oj.uz

Submission #674164

# Submission time Handle Problem Language Result Execution time Memory
674164 2022-12-23T11:02:29 Z QwertyPi Cambridge (info1cup18_cambridge) C++14
55 / 100
 2000 ms 15064 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;
		for(int i = 0; i < n; i++){
			segTree.upd(i, 0, (1 << 30), 0, 0, n - 1);
		}
	}
	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();
	}
};

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;
	}
	vector<query> Q;
	for(int i = 0; i < m; i++){
		int l, r; cin >> l >> r; l--; r--;
		Q.push_back({l, r, i});
	}
	sort(Q.begin(), Q.end());
	int l = 0, r = -1;
	DS::init(n);
	for(auto q : Q){
		while(r < q.r){
			r++;
			DS::add(r);
		}
		while(l > q.l){
			l--;
			DS::add(l);
		}
		while(r > q.r){
			DS::del(r);
			r--;
		}
		while(l < q.l){
			DS::del(l);
			l++;
		}
		ans[q.id] = DS::qry();
	}
	for(int i = 0; i < m; i++){
		cout << ans[i] << endl;
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 103 ms 10408 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 37 ms 1588 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 476 ms 2572 KB Output is correct
4 Correct 1109 ms 4704 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 103 ms 10408 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 37 ms 1588 KB Output is correct
6 Correct 476 ms 2572 KB Output is correct
7 Correct 1109 ms 4704 KB Output is correct
8 Execution timed out 2059 ms 15064 KB Time limit exceeded
9 Halted 0 ms 0 KB -