90分暴力解法:
用线段树,初始值为该天的教室数,每个人来申请的时候在这段区间减去借走的数,然后查询最小值是否小于0,是就输出-1,否则继续。
(其实在vijos是可以直接A的,他们的评测机太快了)
#include <iostream>
#define maxn 1000005
using namespace std;
void scan(int &x)
{
char c;
bool flag = false;
while (!isdigit(c = getchar()))
{
if (c == '-')
flag = true;
}
x = ;
do
x = x * + c - '';
while (isdigit(c = getchar()));
if (flag)
x = -x;
}
int n, m, val[maxn];
namespace seg
{
struct node
{
int val, mark, minimum;
} nds[maxn * ];
void init(int l = , int r = n, int p = )
{
if (l == r)
{
nds[p].minimum = nds[p].val = val[l];
}
else
{
int mid = (l + r) / ;
init(l, mid, p * );
init(mid + , r, p * + );
nds[p].minimum = min(nds[p * ].minimum, nds[p * + ].minimum);
}
}
void add(int l, int r, int val, int p = , int ll = , int rr = n)
{
if (l == ll && r == rr)
{
nds[p].mark += val;
nds[p].minimum += val;
}
else
{
int mid = (ll + rr) / ;
if (l <= mid)
add(l, min(r, mid), val, p * , ll, mid);
if (mid + <= r)
add(max(l, mid + ), r, val, p * + , mid + , rr);
nds[p].minimum = min(nds[p * ].minimum, nds[p * + ].minimum) + nds[p].mark;
}
}
int query(int l, int r, int p = , int ll = , int rr = n)
{
if (l == ll && r == rr)
{
return nds[p].minimum;
}
else
{
int mid = (ll + rr) / ;
int ans = 0x7fffffff;
if (l <= mid)
ans = min(ans, query(l, min(r, mid), p * , ll, mid));
if (mid + <= r)
ans = min(ans, query(max(l, mid + ), r, p * + , mid + , rr));
return ans + nds[p].mark;
}
}
}
int main()
{
ios::sync_with_stdio(false);
scan(n);
scan(m);
for (int i = ; i <= n; i++)
scan(val[i]);
seg::init(,n,);
int d, s, t;
for (int i = ; i <= m; i++)
{
scan(d);
scan(s);
scan(t);
seg::add(s, t, -d);
if (seg::query(s, t) < )
{
cout << - << endl
<< i;
return ;
}
}
cout << ;
return ;
}