oj.uz

Submission #382792

# Submission time Handle Problem Language Result Execution time Memory
382792 2021-03-28T08:17:41 Z pit4h Arranging Tickets (JOI17_arranging_tickets) C++14
0 / 100
 6 ms 4608 KB 
#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];

priority_queue<pii> 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(b[i], a[i]));
	}
	
	int cur_sum = 0, max_sum = 0;
	for(int i=1; i<=n; ++i) {
		cur_sum += sweep[i];	
		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) {
		tree_l[i+base] = min(tree_l[i-1+base], (max_sum - cnt[i])/2);
	}
	for(int i=n; i>=1; --i) {
		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()) {
		pii cur = pq.top();
		swap(cur.st, cur.nd);
		pq.pop();
		if(qry(0, cur.st-1, tree_l, push_l) > 0 && qry(cur.nd+1, n+1, tree_r, push_r) > 0) {
			ans--;	
			ins(0, cur.st-1, -1, tree_l, push_l);
			ins(cur.nd+1, n+1, -1, tree_r, push_r);
		}
	}
	
	cout<<ans<<'\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4588 KB Output is correct
2 Correct 4 ms 4588 KB Output is correct
3 Correct 4 ms 4588 KB Output is correct
4 Correct 4 ms 4588 KB Output is correct
5 Correct 4 ms 4588 KB Output is correct
6 Correct 4 ms 4588 KB Output is correct
7 Correct 4 ms 4588 KB Output is correct
8 Correct 4 ms 4588 KB Output is correct
9 Correct 6 ms 4588 KB Output is correct
10 Correct 4 ms 4588 KB Output is correct
11 Correct 4 ms 4588 KB Output is correct
12 Incorrect 4 ms 4608 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4588 KB Output is correct
2 Correct 4 ms 4588 KB Output is correct
3 Correct 4 ms 4588 KB Output is correct
4 Correct 4 ms 4588 KB Output is correct
5 Correct 4 ms 4588 KB Output is correct
6 Correct 4 ms 4588 KB Output is correct
7 Correct 4 ms 4588 KB Output is correct
8 Correct 4 ms 4588 KB Output is correct
9 Correct 6 ms 4588 KB Output is correct
10 Correct 4 ms 4588 KB Output is correct
11 Correct 4 ms 4588 KB Output is correct
12 Incorrect 4 ms 4608 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4588 KB Output is correct
2 Correct 4 ms 4588 KB Output is correct
3 Correct 4 ms 4588 KB Output is correct
4 Correct 4 ms 4588 KB Output is correct
5 Correct 4 ms 4588 KB Output is correct
6 Correct 4 ms 4588 KB Output is correct
7 Correct 4 ms 4588 KB Output is correct
8 Correct 4 ms 4588 KB Output is correct
9 Correct 6 ms 4588 KB Output is correct
10 Correct 4 ms 4588 KB Output is correct
11 Correct 4 ms 4588 KB Output is correct
12 Incorrect 4 ms 4608 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4588 KB Output is correct
2 Correct 4 ms 4588 KB Output is correct
3 Correct 4 ms 4588 KB Output is correct
4 Correct 4 ms 4588 KB Output is correct
5 Correct 4 ms 4588 KB Output is correct
6 Correct 4 ms 4588 KB Output is correct
7 Correct 4 ms 4588 KB Output is correct
8 Correct 4 ms 4588 KB Output is correct
9 Correct 6 ms 4588 KB Output is correct
10 Correct 4 ms 4588 KB Output is correct
11 Correct 4 ms 4588 KB Output is correct
12 Incorrect 4 ms 4608 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4588 KB Output is correct
2 Correct 4 ms 4588 KB Output is correct
3 Correct 4 ms 4588 KB Output is correct
4 Correct 4 ms 4588 KB Output is correct
5 Correct 4 ms 4588 KB Output is correct
6 Correct 4 ms 4588 KB Output is correct
7 Correct 4 ms 4588 KB Output is correct
8 Correct 4 ms 4588 KB Output is correct
9 Correct 6 ms 4588 KB Output is correct
10 Correct 4 ms 4588 KB Output is correct
11 Correct 4 ms 4588 KB Output is correct
12 Incorrect 4 ms 4608 KB Output isn't correct
13 Halted 0 ms 0 KB -