describe

in one's college years , We often need to rent classrooms . Big to department Events , Small to study group self study discussion , They all need to apply to the school to borrow classrooms . The size and function of the classroom are different , The identity of the students in the classroom is different , The procedures for borrowing a classroom are different .

In the face of massive information about renting classrooms , We naturally want programming to solve this problem . We need to deal with the next n Borrow the classroom information , Among them the first i Day school has ri Classrooms are available for rent . share m Orders , Each order is described in three positive integers , Respectively dj,sj,tj, Indicates that a renter needs to go from sj To the first day tj Rent classroom ( Including the first sj Day and day tj God ), Every day I need to rent dj A classroom .

We assume that , The size of the renter's classroom 、 There is no place for . For each order , We just need to provide... Every day dj A classroom , And which classrooms are they , Whether it's the same classroom or not every day doesn't need to be considered .

The principle of borrowing a classroom is first come first served , That is to say, we need to assign classrooms to each order in order of order . If an order cannot be fully met during the allocation process , Then we need to stop the allocation of classrooms , Inform the current applicant to modify the order . Here's unsatisfied means from the sj To the first day tj At least one day of the day there are not enough classrooms left dj individual .

Now we need to know , Whether there will be orders that cannot be fully met . If there is , Which applicant needs to be informed to modify the order .

Format

Input format

The first line contains two positive integers n,m, Indicates the number of days and the number of orders .

The second line contains n A positive integer , Among them the first i The number is ri, It means the first one i The number of classrooms available for rent per day .

Next there is m That's ok , Each line contains three positive integers dj,sj,tj, Indicates the number of rentals , Start of lease 、 The end is on the day after .

Two adjacent numbers in each row are separated by a space . Days and orders are from 1 Starting integer number .

Output format

If all orders are met , There is only one line of output , Contains an integer 0. otherwise ( The order can't be fully satisfied ) Output two lines , The first line outputs a negative integer -1, The second line outputs the applicant number of the order to be modified .

The sample input

4 3
2 5 4 3
2 1 3
3 2 4
4 2 4

Sample output

-1
2

Limit

Every test point 1s

Tips

about 10% The data of , Yes 1≤ n,m≤ 10;

about 30% The data of , Yes 1≤ n,m≤1000;

about 70% The data of , Yes 1≤ n,m≤ 10^5;

about 100% The data of , Yes 1≤n,m≤10^6,0≤ri,dj≤10^9,1≤sj≤tj≤n.

Although the positive solution is a line segment tree of infinite card constants , But I went through it with a differential sequence ……

The specific method is to input data first , Use difference sequence to judge whether it will explode or not , If it's not obvious, it's direct output 0. Otherwise, two questions , Judge if it's exploding

efficiency O(nlogm)

#include<cstdio>
inline int read()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
struct structure{
int l,r,k;
}dat[1000001];
int s[1000002];
int a[1000002];
int n,q;
inline bool mark(int x)
{
int sum=0;
for (int i=1;i<=n;i++)s[i]=a[i]-a[i-1];
for (int i=1;i<=x;i++)
{
s[dat[i].l]-=dat[i].k;
s[dat[i].r+1]+=dat[i].k;
}
for (int i=1;i<=n;i++)
{
sum+=s[i];
if (sum<0) return 0;
}
return 1;
}
inline int divide(int x)
{
int l=1,r=x,ans;
while (l<=r)
{
int mid=(l+r)>>1;
if (!mark(mid)) {ans=mid;r=mid-1;}
else l=mid+1;
}
return ans;
}
int main()
{
n=read();
q=read();
for (int i=1;i<=n;i++)
{
a[i]=read();
s[i]=a[i]-a[i-1];
}
printf("\n");
for (int i=1;i<=q;i++)
{
dat[i].k=read();
dat[i].l=read();
dat[i].r=read();
s[dat[i].l]-=dat[i].k;
s[dat[i].r+1]+=dat[i].k;
}
int sum=0;
for (int i=1;i<=n;i++){sum+=s[i];if (sum<0) break;}
if (sum>=0){printf("0");return 0;}
printf("-1\n%d",divide(q));
}

vijos1782 Borrow more related articles from the classroom

  1. vijos1782: Borrow the classroom

    describe in one's college years , We often need to rent classrooms . Big to department Events , Small to study group self study discussion , They all need to apply to the school to borrow classrooms . The size and function of the classroom are different , The identity of the students in the classroom is different , The procedures for borrowing a classroom are different . In the face of massive information about renting classrooms , We naturally hope that ...

  2. [vijos1782] Borrow the classroom &lt; Line segment tree &gt;

      Topic link :https://vijos.org/p/1782 The question : An interval 1,n.m operations , Each operation makes l,r Interval minus d, When any value is less than 0 On the output, which is the current operation There is no difficulty in this problem , yes ...

  3. NOIP2012 Borrow the classroom [ Line segment tree | offline Difference Two points answer ]

    Title Description in one's college years , We often need to rent classrooms . Big to department Events , Small to study group self study discussion , Need to be Apply to the school for the classroom . The size and function of the classroom are different , The identity of the students in the classroom is different , The procedures for borrowing a classroom are different . In the face of massive information about renting classrooms , We are from ...

  4. [NOIP2012] Improvement group Luogu P1083 Borrow the classroom

    Title Description in one's college years , We often need to rent classrooms . Big to department Events , Small to study group self study discussion , They all need to apply to the school to borrow classrooms . The size and function of the classroom are different , The identity of the students in the classroom is different , The procedures for borrowing a classroom are different . In the face of massive information about renting classrooms , We naturally ...

  5. Borrow the classroom (codevs 1217)

    1217 Borrow the classroom 2012 year NOIP National League improvement section   The time limit : 1 s   Space restriction : 128000 KB   Question level : diamond Diamond Answer key   View the run results     Title Description  Descrip ...

  6. NOIp 2012 #2 Borrow the classroom Label: Interval modify segment tree

    Title Description in one's college years , We often need to rent classrooms . Big to department Events , Small to study group self study discussion , They all need to apply to the school to borrow classrooms . The size and function of the classroom are different , The identity of the students in the classroom is different , The procedures for borrowing a classroom are different . In the face of massive information about renting classrooms , We naturally ...

  7. NOIP 2012 Day2T2 In the classroom

    NOIP 2012 Day2T2 In the classroom Subject portal :http://codevs.cn/problem/1217/ Title Description  Description in one's college years , We often need to rent classrooms . Big to department Events ...

  8. 【NOIP2012】 Borrow the classroom

    Because our school OJ+1s So we use the line segment tree to cross the water , Don't go to syz I really don't know the problem of reservoir water = = The original title is : in one's college years , We often need to rent classrooms . Big to department Events , Small to study group self study discussion , Need to be Apply to the school for the classroom . Classroom ...

  9. NOIP 2012 T5 Borrow the classroom [ Luogu P1083]

    Title Description in one's college years , We often need to rent classrooms . Big to department Events , Small to study group self study discussion , Need to be Apply to the school for the classroom . The size and function of the classroom are different , The identity of the students in the classroom is different , The procedures for borrowing a classroom are different . In the face of massive information about renting classrooms , We are from ...

Random recommendation

  1. R Language crawler's first attempt - be based on RVEST Package learning

    Be careful : This article is 2 Written in the month of , Lagou has been revised a long time ago , The code has failed , That's what you mean , It mainly depends on how to use the code .. Another crawler that has been in use and maintained recently is KINDLE Special book crawler ,blog See here for the address : http://w ...

  2. stay Visual Studio Set multi-core parallel compilation in

    VS Is a very powerful and practical IDE, Is in Windows The preferred software for learning programming under the environment of . Sometimes it takes a long time to compile a larger project , It may take nearly a minute to compile just by modifying the code , Even more . Even with incremental compilation on ...

  3. Samba After sharing the file in Windows Inaccessible issues on

    /etc/samba/smb.conf The configuration is as follows : #============================ Share Definitions ========================== ...

  4. paper 94: Blog resources in visual field 1 The Chinese part of

    This is the first part of the blog resources in the field of image vision , contain : In mainland China . Hong Kong . Taiwan These celebrities are generally familiar with , This article only includes personal blogs with more information , And there are a lot of updates , There are also celebrities who share paper.code Or the dataset doesn't ...

  5. Android OpenGL ES( Ten ) Draw triangle Triangle .

    The triangle is OpenGL ES The support side , Also create a DrawTriangle Activity, Definition 6 Three vertices use three different modes to draw triangles : float vertexArray[] = { -0.8f, - ...

  6. 《React Native Understanding and actual combat 》 Book serials 「iOS Platform and React Native Hybrid development 」

    This is my published book <React Native Understanding and actual combat > Serial sharing , This book is published by China Machine Press , It's explained in detail in the book React Native The bottom principle of the frame .React Native Component layout . Components and ...

  7. Abp zero Sample run

    https://aspnetboilerplate.com/Pages/Documents/Zero/Startup-Template-Core Introduction The easiest wa ...

  8. Django Create the first project

    Create project : [root@localhost ~]$ django-admin.py startproject web # web Project name [root@localhost ~]$ tree web/ w ...

  9. .NET Interview treasure - senior 2

    http://blog.csdn.net/shanyongxu/article/category/6023593 about Web performance optimization , Do you have any knowledge and experience ? 1. Front end optimization (1) Reduce  HTTP please ...

  10. Win10 How to create a new user, how to add a new account

    https://jingyan.baidu.com/article/25648fc162d5899190fd0069.html A lot of friends have installed it Windows10 After the system , Use the super administrator account to login the system directly ...