## 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 .

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

```-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>
{
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()
{
for (int i=1;i<=n;i++)
{
s[i]=a[i]-a[i-1];
}
printf("\n");
for (int i=1;i<=q;i++)
{
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 ...