#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int, int>
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 11;
const int B = 800;
int t[MAXN], d[MAXN];
int ans[MAXN], to[MAXN];
struct query{
int l, r, id;
bool operator< (const query& o) const {
if(l / B != o.l / B)
return l / B < o.l / B;
else if(r != o.r)
return l / B % 2 == 0 ? r < o.r : r > o.r;
else
return id < o.id;
}
};
namespace DS{
struct SegTree{
int mx[MAXN << 3] = {0}, s[MAXN << 3] = {0};
void upd(int pos, int t, int d, int v, int tl, int tr){
if(tl == tr) { mx[v] = t - d, s[v] = t; return; }
int tm = (tl + tr) / 2;
if(pos <= tm){
upd(pos, t, d, v * 2 + 1, tl, tm);
}else{
upd(pos, t, d, v * 2 + 2, tm + 1, tr);
}
mx[v] = max(mx[v * 2 + 1], s[v * 2 + 1] + mx[v * 2 + 2]);
s[v] = s[v * 2 + 1] + s[v * 2 + 2];
}
bool qry(){
return mx[0] < 0;
}
} segTree;
int n;
void init(int n){
DS::n = n;
fill(segTree.mx, segTree.mx + (MAXN << 3), -(1 << 30));
fill(segTree.s, segTree.s + (MAXN << 3), 0);
}
void add(int idx){
// cout << "ADD " << idx << endl;
idx = to[idx];
segTree.upd(idx, t[idx], d[idx], 0, 0, n - 1);
}
void del(int idx){
// cout << "DEL " << idx << endl;
idx = to[idx];
segTree.upd(idx, 0, (1 << 30), 0, 0, n - 1);
}
int qry(){
// cout << "QRY" << endl;
return segTree.qry();
}
};
int ml[MAXN];
int32_t main(){
int n, m; cin >> n >> m;
for(int i = 0; i < n; i++){
cin >> t[i] >> d[i];
}
vector<pair<pair<int, int>, int>> v;
for(int i = 0; i < n; i++){
v.push_back({{d[i], t[i]}, i});
}
sort(v.begin(), v.end());
for(int i = 0; i < n; i++){
to[v[i].se] = i;
d[i] = v[i].fi.fi;
t[i] = v[i].fi.se;
}
int l = 0, r = -1;
DS::init(n);
for(int i = 0; i < n; i++){
DS::add(++r);
cout << DS::qry() << endl;
while(DS::qry() == 0){
DS::del(l++);
}
ml[r] = l;
}
for(int i = 0; i < m; i++){
int l, r; cin >> l >> r; l--; r--;
cout << (l >= ml[r]) << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
12756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
12756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
12756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
12756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
