oj.uz

Submission #674174

# Submission time Handle Problem Language Result Execution time Memory
674174 2022-12-23T11:17:54 Z QwertyPi Cambridge (info1cup18_cambridge) C++14
100 / 100
 303 ms 22048 KB 
#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);
		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;
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 6 ms 12904 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 6 ms 12904 KB Output is correct
3 Correct 114 ms 18804 KB Output is correct
4 Correct 7 ms 12884 KB Output is correct
5 Correct 16 ms 13640 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 6 ms 12904 KB Output is correct
3 Correct 86 ms 13212 KB Output is correct
4 Correct 169 ms 13408 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 6 ms 12904 KB Output is correct
3 Correct 114 ms 18804 KB Output is correct
4 Correct 7 ms 12884 KB Output is correct
5 Correct 16 ms 13640 KB Output is correct
6 Correct 86 ms 13212 KB Output is correct
7 Correct 169 ms 13408 KB Output is correct
8 Correct 297 ms 18812 KB Output is correct
9 Correct 286 ms 21480 KB Output is correct
10 Correct 297 ms 21484 KB Output is correct
11 Correct 287 ms 22048 KB Output is correct
12 Correct 303 ms 21520 KB Output is correct
13 Correct 6 ms 12884 KB Output is correct