oj.uz

Submission #110686

# Submission time Handle Problem Language Result Execution time Memory
110686 2019-05-12T00:50:33 Z wilwxk Jousting tournament (IOI12_tournament) C++11
100 / 100
 159 ms 8440 KB 
#include <bits/stdc++.h>
using namespace std;

struct node {
	int s, lz;
};

const int MAXN=1e5+5;
int qini[MAXN], qfim[MAXN];
pair<int, int> qv[MAXN];
multiset<int> s;
node seg[MAXN*4];
int v[MAXN];
int n, m, cara, conta;
int respf, maior;

void refresh(int sind, int ini, int fim) {
	if(!seg[sind].lz) return;
	seg[sind].s=0;
	seg[sind].lz=0;
	if(ini==fim) return;
	int e=sind*2; int d=e+1;
	seg[e].lz=seg[d].lz=1;
}

void update(int sind, int ini, int fim, int qini, int qfim) {
	refresh(sind, ini, fim);
	if(qini>fim||qfim<ini) return;
	if(qini<=ini&&qfim>=fim) {
		seg[sind].lz=1;
		refresh(sind, ini, fim);
		return;
	}
	int m=(ini+fim)/2; int e=sind*2; int d=e+1;
	update(e, ini, m, qini, qfim);
	update(d, m+1, fim, qini, qfim);
	seg[sind].s=seg[e].s+seg[d].s;
}

int query(int sind, int ini, int fim, int val, int k) {
	refresh(sind, ini, fim);
	if(ini==fim) return seg[sind].s==val;
	int m=(ini+fim)/2; int e=sind*2; int d=e+1;
	refresh(e, ini, m); refresh(d, m+1, fim);
	if(k==1) {
		if(seg[e].s>=val) return query(e, ini, m, val, k);
		else return (m-ini+1)+query(d, m+1, fim, val-seg[e].s, k);
	}
	else {
		if(seg[e].s>val) return query(e, ini, m, val, k);
		else return (m-ini+1)+query(d, m+1, fim, val-seg[e].s, k);
	}
}

void build(int sind, int ini, int fim) {
	if(ini==fim) {
		seg[sind].s=1;
		return;
	}
	int m=(ini+fim)/2; int e=sind*2; int d=e+1;
	build(e, ini, m); build(d, m+1, fim);
	seg[sind].s=seg[e].s+seg[d].s;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	n=N; m=C; cara=R;
	for(int i=1; i<=n; i++) v[i]=K[i-1]<cara;
	for(int i=1; i<=m; i++) qini[i]=S[i-1]+1, qfim[i]=E[i-1]+1;
	build(1, 1, n);

	for(int i=1; i<=m; i++) {
		int ini=query(1, 1, n, qini[i], 1);
		int fim=query(1, 1, n, qfim[i], 2);
		qini[i]=ini; qfim[i]=fim;
		qv[i]={ini, fim};
		update(1, 1, n, ini+1, fim);
	}
	sort(qv+1, qv+1+m);
	qv[m+1].first=qv[m+1].second=1e9;

	int fim=0; int ind=0;
	while(v[fim+1]) fim++; fim++;
	for(int i=1; i<=n; i++) {
		if(i==fim+1) {
			fim=i-1;
			while(v[fim+1]) fim++; fim++;
			s.clear();
		}
		//printf("sendo %d (fim=%d)...\n", i, fim);
		while(s.size()&&*s.begin()<i) s.erase(s.begin()); 
		while(qv[ind+1].first<=i) {
			ind++;
			//printf("  add qv[%d] (%d %d)\n", ind, qv[ind].first, qv[ind].second);
			if(qv[ind].second>fim) continue;
			s.insert(qv[ind].second);
		}
		//printf("  %d > %d\n", i, s.size());
		if(s.size()>maior) maior=s.size(), respf=i-1;
	}

	return respf;
}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:82:2: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  while(v[fim+1]) fim++; fim++;
  ^~~~~
tournament.cpp:82:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  while(v[fim+1]) fim++; fim++;
                         ^~~
tournament.cpp:86:4: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
    while(v[fim+1]) fim++; fim++;
    ^~~~~
tournament.cpp:86:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
    while(v[fim+1]) fim++; fim++;
                           ^~~
tournament.cpp:98:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(s.size()>maior) maior=s.size(), respf=i-1;
      ~~~~~~~~^~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 8 ms 768 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 9 ms 640 KB Output is correct
5 Correct 7 ms 640 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Correct 8 ms 768 KB Output is correct
8 Correct 7 ms 640 KB Output is correct
9 Correct 4 ms 580 KB Output is correct
10 Correct 8 ms 768 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2552 KB Output is correct
2 Correct 159 ms 8440 KB Output is correct
3 Correct 26 ms 3968 KB Output is correct
4 Correct 103 ms 7664 KB Output is correct
5 Correct 96 ms 7708 KB Output is correct
6 Correct 76 ms 5880 KB Output is correct
7 Correct 139 ms 8184 KB Output is correct
8 Correct 96 ms 7928 KB Output is correct
9 Correct 20 ms 3712 KB Output is correct
10 Correct 23 ms 3960 KB Output is correct