oj.uz

Submission #73833

# Submission time Handle Problem Language Result Execution time Memory
73833 2018-08-29T06:11:16 Z FLDutchman Jousting tournament (IOI12_tournament) C++14
100 / 100
 134 ms 20404 KB 
#include <bits/stdc++.h>
using namespace std;

typedef int INT;

#define pb push_back
#define fst first
#define snd second
#define FOR(i,l,r) for(int i = (l); i < (r); i++)

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

void prop(int,int,int);

vi tsum, tmax, lazy;
vi arr;

void upds(int n){
	tsum[n] = tsum[n<<1] + tsum[n<<1|1];
}

void buildsum(int lb, int rb, int n){
	if(lb+1==rb) {
		tsum[n] = 1;
		return;
	}
	int mb = (lb+rb)/2;
	buildsum(lb,mb,n<<1);
	buildsum(mb,rb,n<<1|1);
	upds(n);
}

void add(int l, int r, int lb, int rb, int n){
	//cerr<<l<<" "<<r<<" "<<lb<<" "<<rb<<" "<<n<<endl;
	if(l <= lb and rb <= r) {
		lazy[n] = 1;
		tsum[n] = 0;
		return;
	}
	if(lazy[n]) prop(lb,rb,n);
	int mb = (lb+rb)/2;
	if(l < mb) add(l,r,lb,mb,n<<1);
	if(r > mb) add(l,r,mb,rb,n<<1|1);
	upds(n);
}

void prop(int lb, int rb, int n){
	int mb = (lb+rb)/2;
	add(lb,rb,lb,mb,n<<1);
	add(lb,rb,mb,rb,n<<1|1);
	lazy[n] = 0;
}

int getidx(int i, int lb, int rb, int n){
	if(lb + 1 == rb) return lb;
	if(lazy[n]) prop(lb,rb,n);
	if(i == tsum[n]) return rb;
	int mb = (lb+rb)/2;
	if(i < tsum[n<<1]) return getidx(i, lb, mb, n<<1);
	return getidx(i-tsum[n<<1], mb,rb,n<<1|1);
}

void updm(int n){
	tmax[n] = max(tmax[n<<1], tmax[n<<1|1]);
}

void buildmax(int lb, int rb, int n){
	if(lb+1==rb){
		tmax[n] = arr[lb];
		return;
	}
	int mb = (lb+rb)/2;
	buildmax(lb,mb,n<<1);
	buildmax(mb,rb,n<<1|1);
	updm(n);
}

int rmq(int l, int r, int lb, int rb, int n){
	//cout<<l<<" "<<r<<" " <<lb<<" "<< rb<<" " << n << endl;
	if(l <= lb and rb <= r) return tmax[n];
	int mb = (lb+rb)/2;
	int res = -1;
	if(l < mb) res = max(res, rmq(l,r,lb,mb,n<<1));
	if(r > mb) res = max(res, rmq(l,r,mb,rb,n<<1|1));
	return res;
}

vii intervals;

vii idx;

INT GetBestPosition(INT N, INT C, INT R, INT *K, INT *S, INT *E) {
	idx.resize(N);
	lazy.assign(4*N,0);
	tsum.assign(4*N,0);
	tmax.assign(4*N,0);
	buildsum(0, N, 1);

	FOR(i,0,N-1) arr.pb(K[i]);
	buildmax(0,N-1,1);
	FOR(i, 0, N) idx[i] = {i,i};
	FOR(i, 0, C){
		int l = getidx(S[i], 0,N,1), r = getidx(E[i]+1, 0, N, 1) - 1;
		intervals.pb({l,r});
		add(l+1,r+1,0,N,1);
		//cout<<tsum[1]<<endl;
	}
	//for(ii p : intervals) cout << p.fst << " " << p.snd << endl;
	vii q;
	vi val(C, -1);
	//cout<<"rmq "<<rmq(0,4,0,4,1)<<endl;
	FOR(i, 0, C) {
		ii inter = intervals[i];
		val[i] = rmq(intervals[i].fst, intervals[i].snd, 0, N-1, 1);
		if(val[i] < R) {
			q.pb({inter.fst, 1});
			q.pb({inter.snd+1, -1});
		}
	}
	
	sort(q.begin(), q.end());

	ii best = {-1, -1e9};

	//for(int k : val) cout << k << endl;
	int tot = 0, j = 0;;	
	FOR(i, 0, N) {
		for(; j < q.size() and q[j].fst <= i; j++) tot += q[j].snd; 
			//cout<<tot<<endl;
		best = max(best, {tot,-i});
	}
	return -best.snd;
}

Compilation message

tournament.cpp: In function 'INT GetBestPosition(INT, INT, INT, INT*, INT*, INT*)':
tournament.cpp:131:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; j < q.size() and q[j].fst <= i; j++) tot += q[j].snd; 
         ~~^~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 4 ms 484 KB Output is correct
4 Correct 3 ms 484 KB Output is correct
5 Correct 3 ms 544 KB Output is correct
6 Correct 3 ms 544 KB Output is correct
7 Correct 3 ms 620 KB Output is correct
8 Correct 4 ms 624 KB Output is correct
9 Correct 4 ms 624 KB Output is correct
10 Correct 3 ms 624 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 624 KB Output is correct
2 Correct 8 ms 1004 KB Output is correct
3 Correct 5 ms 1004 KB Output is correct
4 Correct 8 ms 1004 KB Output is correct
5 Correct 9 ms 1004 KB Output is correct
6 Correct 7 ms 1004 KB Output is correct
7 Correct 8 ms 1132 KB Output is correct
8 Correct 10 ms 1132 KB Output is correct
9 Correct 3 ms 1132 KB Output is correct
10 Correct 9 ms 1132 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 5096 KB Output is correct
2 Correct 126 ms 11360 KB Output is correct
3 Correct 32 ms 11360 KB Output is correct
4 Correct 117 ms 14252 KB Output is correct
5 Correct 119 ms 15512 KB Output is correct
6 Correct 125 ms 16136 KB Output is correct
7 Correct 132 ms 18908 KB Output is correct
8 Correct 134 ms 20404 KB Output is correct
9 Correct 40 ms 20404 KB Output is correct
10 Correct 35 ms 20404 KB Output is correct