oj.uz

Submission #793479

# Submission time Handle Problem Language Result Execution time Memory
793479 2023-07-25T22:20:41 Z Username4132 Teams (IOI15_teams) C++14
100 / 100
 1632 ms 387568 KB 
#include "teams.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

struct Vertex{
	int value;
	Vertex *l, *r;
	Vertex(int _value) : value(_value), l(NULL), r(NULL) {}
	Vertex(Vertex* _l, Vertex* _r) : value(_l->value + _r->value), l(_l), r(_r) {}
};

Vertex* build(int tl, int tr){
	if(tl==tr) return new Vertex(0);
	int tm = (tl+tr)>>1;
	return new Vertex(build(tl, tm), build(tm+1, tr));
}

Vertex* update(Vertex* v, int tl, int tr, int pos, int delta){
	if(tl==tr) return new Vertex(v->value + delta);
	int tm = (tl+tr)>>1;
	if(pos<=tm) return new Vertex(update(v->l, tl, tm, pos, delta), v->r);
	else return new Vertex(v->l, update(v->r, tm+1, tr, pos, delta));
}

int query(Vertex* v, int l, int r, int tl, int tr){
	if(l>r) return 0;
	if(l==tl && r==tr) return v->value;
	int tm = (tl+tr)>>1;
	return query(v->l, l, min(r, tm), tl, tm) + query(v->r, max(l, tm+1), r, tm+1, tr);
}

pii srch(Vertex* vl, Vertex* vr, int tl, int tr, int target){
	assert(target>0);
	if(tl==tr) return {tl, target};
	int tm = (tl+tr)>>1;
	int sum = vr->l->value - vl->l->value;
	if(sum < target) return srch(vl->r, vr->r, tm+1, tr, target-sum);
	else return srch(vl->l, vr->l, tl, tm, target);
}

const int MAXN = 500010;
int n;
Vertex* roots[MAXN];
vector<int> vals[MAXN];

void init(int N, int A[], int B[]) {
	n=N;
	roots[0]=build(0, n+4);
	forn(i, n) vals[A[i]].PB(B[i]);
	forsn(i, 1, n+1){
		roots[i]=roots[i-1];
		for(int el:vals[i]) roots[i]=update(roots[i], 0, n+4, el, 1);
	}
}

int cou(int x1, int x2, int y1, int y2){
	return query(roots[max(x2-1, 0)], y1, y2-1, 0, n+4) - query(roots[max(x1-1, 0)], y1, y2-1, 0, n+4);
}

pii binary(int x1, int x2, int bound){
	return srch(roots[max(x1-1, 0)], roots[max(x2-1, 0)], 0, n+4, bound);
}

bool solve(vector<pii>& dom, vector<int>& xt, pii ins, int target){
	int del=0;
	while(ins.S >= dom.back().S){
		if(ins.S == dom.back().S) del=xt.back();
		dom.pop_back();
		xt.pop_back();
	}
	while(true){
		int obt = cou(dom.back().F + 1, ins.F + 1, ins.S, dom.back().S) - del;
		if(obt < target){
			target-=obt;
			ins.S=dom.back().S;
			del=xt.back();
			dom.pop_back();
			xt.pop_back();
		}
		else{
			int base = cou(dom.back().F + 1, ins.F + 1, 0, ins.S) + del;
			pii res = binary(dom.back().F + 1, ins.F + 1, target + base);
			dom.PB({ins.F, res.F});
			xt.PB(res.S);
			return true;
		}
		if(dom.empty()) return false;
	}
}

int can(int m, int arr[]) {
	int dummy=0;
	forn(i, m){
		dummy+=arr[i];
		if(dummy>n) return 0;
	}
	sort(arr, arr+m);
	vector<pii> dom;
	vector<int> xt;
	dom.PB({-1, n+2});
	xt.PB(0);
	int cnt=0;
	forn(i, m){
		++cnt;
		if(i==m-1 || arr[i]!=arr[i+1]){
			if(!solve(dom, xt, {arr[i], arr[i]}, cnt*arr[i])){
				return 0;
			}
			cnt=0;
		}
	}
	return 1;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12124 KB Output is correct
2 Correct 6 ms 12064 KB Output is correct
3 Correct 6 ms 12096 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 12052 KB Output is correct
6 Correct 6 ms 12068 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 7 ms 12084 KB Output is correct
9 Correct 6 ms 12052 KB Output is correct
10 Correct 6 ms 11992 KB Output is correct
11 Correct 6 ms 12064 KB Output is correct
12 Correct 6 ms 12060 KB Output is correct
13 Correct 6 ms 12056 KB Output is correct
14 Correct 6 ms 12060 KB Output is correct
15 Correct 7 ms 11988 KB Output is correct
16 Correct 6 ms 11988 KB Output is correct
17 Correct 6 ms 12060 KB Output is correct
18 Correct 6 ms 11996 KB Output is correct
19 Correct 6 ms 11980 KB Output is correct
20 Correct 6 ms 11996 KB Output is correct
21 Correct 6 ms 11988 KB Output is correct
22 Correct 8 ms 11992 KB Output is correct
23 Correct 6 ms 12052 KB Output is correct
24 Correct 6 ms 11988 KB Output is correct
25 Correct 6 ms 12056 KB Output is correct
26 Correct 6 ms 11988 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 78152 KB Output is correct
2 Correct 111 ms 78168 KB Output is correct
3 Correct 115 ms 78212 KB Output is correct
4 Correct 119 ms 78768 KB Output is correct
5 Correct 65 ms 76592 KB Output is correct
6 Correct 66 ms 76640 KB Output is correct
7 Correct 67 ms 76584 KB Output is correct
8 Correct 67 ms 76544 KB Output is correct
9 Correct 83 ms 77504 KB Output is correct
10 Correct 84 ms 77140 KB Output is correct
11 Correct 64 ms 77200 KB Output is correct
12 Correct 67 ms 77248 KB Output is correct
13 Correct 74 ms 77588 KB Output is correct
14 Correct 109 ms 77844 KB Output is correct
15 Correct 115 ms 77984 KB Output is correct
16 Correct 103 ms 78040 KB Output is correct
17 Correct 69 ms 76796 KB Output is correct
18 Correct 73 ms 76664 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 78932 KB Output is correct
2 Correct 117 ms 78932 KB Output is correct
3 Correct 345 ms 82236 KB Output is correct
4 Correct 114 ms 78796 KB Output is correct
5 Correct 135 ms 77380 KB Output is correct
6 Correct 116 ms 77324 KB Output is correct
7 Correct 70 ms 77316 KB Output is correct
8 Correct 104 ms 77324 KB Output is correct
9 Correct 63 ms 77548 KB Output is correct
10 Correct 67 ms 77668 KB Output is correct
11 Correct 87 ms 77892 KB Output is correct
12 Correct 128 ms 78156 KB Output is correct
13 Correct 195 ms 78704 KB Output is correct
14 Correct 413 ms 80668 KB Output is correct
15 Correct 149 ms 78780 KB Output is correct
16 Correct 157 ms 78876 KB Output is correct
17 Correct 98 ms 77616 KB Output is correct
18 Correct 94 ms 76784 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 380656 KB Output is correct
2 Correct 843 ms 380620 KB Output is correct
3 Correct 1542 ms 387568 KB Output is correct
4 Correct 770 ms 380380 KB Output is correct
5 Correct 493 ms 371616 KB Output is correct
6 Correct 436 ms 371660 KB Output is correct
7 Correct 320 ms 371664 KB Output is correct
8 Correct 412 ms 371708 KB Output is correct
9 Correct 324 ms 371628 KB Output is correct
10 Correct 306 ms 370052 KB Output is correct
11 Correct 356 ms 370644 KB Output is correct
12 Correct 508 ms 371684 KB Output is correct
13 Correct 773 ms 374616 KB Output is correct
14 Correct 1632 ms 383108 KB Output is correct
15 Correct 700 ms 379204 KB Output is correct
16 Correct 703 ms 379284 KB Output is correct
17 Correct 409 ms 373924 KB Output is correct
18 Correct 430 ms 373892 KB Output is correct