Submission #382887

#	Time	Username	Problem	Language	Result	Execution time	Memory
382887		pit4h	Arranging Tickets (JOI17_arranging_tickets)	C++14	85 / 100	204 ms	13280 KiB

arranging_tickets

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
using namespace std;
using pii = pair<int, int>;
const int MAXN = 2e5+2, MAXM = 1e5+2;
int n, m;
int a[MAXM], b[MAXM], c[MAXM];
int cnt[MAXN], sweep[MAXN];

int pref[MAXN], suf[MAXN];
bool flip[MAXM];

priority_queue<pair<pii, int>> pq;

const int base = (1<<18);
int tree_l[2*base+1], tree_r[2*base+1], push_l[2*base+1], push_r[2*base+1];
void upd(int id, int val, int (&tree)[2*base+1], int (&push)[2*base+1]) {
	tree[id] += val;
	push[id] += val;
}
void ins(int l, int r, int val, int (&tree)[2*base+1], int (&push)[2*base+1], int id=1, int rl=0, int rr=base-1) {
	if(l > rr || r < rl) return;
	if(l<=rl && r>=rr) {
		upd(id, val, tree, push);	
		return;
	}
	upd(id*2, push[id], tree, push), upd(id*2+1, push[id], tree, push);
	push[id] = 0;
	ins(l, r, val, tree, push, id*2, rl, (rl+rr)/2), ins(l, r, val, tree, push, id*2+1, (rl+rr)/2+1, rr);	
	tree[id] = min(tree[id*2], tree[id*2+1]);
}
int qry(int l, int r, int (&tree)[2*base+1], int (&push)[2*base+1], int id=1, int rl=0, int rr=base-1) {
	if(l > rr || r < rl) return m;
	if(l<=rl && r>=rr) {
		return tree[id];	
	}
	upd(id*2, push[id], tree, push), upd(id*2+1, push[id], tree, push);
	push[id] = 0;
	return min(qry(l, r, tree, push, id*2, rl, (rl+rr)/2), qry(l, r, tree, push, id*2+1, (rl+rr)/2+1, rr));
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=0; i<m; ++i) {
		cin>>a[i]>>b[i]>>c[i];
		if(a[i] > b[i]) {
			swap(a[i], b[i]);
		}
		b[i]--;
		sweep[a[i]]++;
		sweep[b[i]+1]--;
		pq.push(mp(mp(b[i], a[i]), i));
	}
	
	int cur_sum = 0, max_sum = 0;
	for(int i=1; i<=n; ++i) {
		cur_sum += sweep[i];	
		sweep[i] = 0;
		cnt[i] = cur_sum;
		max_sum = max(max_sum, cnt[i]);
	}

	for(int i=1; i<2*base; ++i) {
		tree_l[i] = tree_r[i] = (max_sum)/2;
	}
	for(int i=1; i<=n; ++i) {
		if(cnt[i] == max_sum) tree_l[i+base] = 0;
		else tree_l[i+base] = min(tree_l[i-1+base], (max_sum - cnt[i])/2);
	}
	for(int i=n; i>=1; --i) {
		if(cnt[i] == max_sum) tree_r[i+base] = 0;
		else tree_r[i+base] = min(tree_r[i+1+base], (max_sum - cnt[i])/2);
	}
	for(int i=base-1; i>=1; --i) {
		tree_l[i] = min(tree_l[i*2], tree_l[i*2+1]);
		tree_r[i] = min(tree_r[i*2], tree_r[i*2+1]);
	}

	int ans = max_sum;
	while(pq.size()) {
		auto cur = pq.top();
		swap(cur.st.st, cur.st.nd);
		pq.pop();
		if(qry(0, cur.st.st-1, tree_l, push_l) > 0 && qry(cur.st.nd+1, n+1, tree_r, push_r) > 0) {
			flip[cur.nd] = 1;
			ans--;	
			ins(0, cur.st.st-1, -1, tree_l, push_l);
			ins(cur.st.nd+1, n+1, -1, tree_r, push_r);
		}
	}
	for(int i=0; i<m; ++i) {
		if(!flip[i]) {
			sweep[a[i]]++;
			sweep[b[i]+1]--;
		}
		else {
			sweep[b[i]+1]++;
			sweep[n+1]--;
			sweep[1]++;
			sweep[a[i]]--;
		}
	}
	cur_sum = 0;
	max_sum = 0;
	for(int i=1; i<=n; ++i) {
		cur_sum += sweep[i];
		sweep[i] = 0;
		cnt[i] = cur_sum;
		max_sum = max(max_sum, cnt[i]);
	}
	
	int l = n+1, r = 0;
	for(int i=1; i<=n; ++i) {
		if(cnt[i] == max_sum) {
			l = min(l, i);	
			r = i;
		}
	}

	int cand1=-1, cand2=-1;
	for(int i=0; i<m; ++i) {
		if(!flip[i] && a[i] <= l && b[i] >= r) {
			if(cand1==-1 || a[i] < a[cand1]) {
				cand1 = i;
			}
			if(cand2==-1 || b[i] > b[cand2]) {
				cand2 = i;
			}
		}
	}
	
	if(cand1!=-1 && cand2!=-1 && cand1 != cand2) {
		max_sum = 0;
		for(int i=1; i<a[cand1]; ++i) {
			max_sum = max(max_sum, cnt[i]+2);
		}
		for(int i=b[cand2]+1; i<=n; ++i) {
			max_sum = max(max_sum, cnt[i]+2);
		}
		if(max_sum < ans) {
			ans--;
		}
	}
	
	cout<<ans<<'\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 35 / 35
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 15