Submission #674160

#	Time	Username	Problem	Language	Result	Execution time	Memory
674160		QwertyPi	Cambridge (info1cup18_cambridge)	C++14	40 / 100	107 ms	10808 KiB

cambridge

#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 pm(int a, int b){
	return b == 0 ? 1 : pm(a * a % MOD, b / 2) * (b % 2 ? a : 1) % MOD;
}

int mi(int a){
	return pm(a, MOD - 2);
}

map<int, int> M; int s = 0;
int f[MAXN];
int t[MAXN], d[MAXN];
int ans[MAXN], to[MAXN];

struct query{
	int l, r, id;
	bool operator< (const query& o) const {
		return l / B < o.l / B || (l / B % 2 == 0 ? r < o.r : r > o.r);
	}
};

namespace DS{

	struct SegTree{
		int mx[MAXN << 2] = {0}, s[MAXN << 2] = {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 / 15
• Subtask 2: 25 / 25
• Subtask 3: 0 / 15
• Subtask 4: 0 / 45