oj.uz

Submission #127472

# Submission time Handle Problem Language Result Execution time Memory
127472 2019-07-09T12:01:31 Z ekrem Teams (IOI15_teams) C++
100 / 100
 1590 ms 376932 KB 
#include "teams.h"
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define MAXN 10000005
using namespace std;

typedef long long ll;
typedef pair < int , int > ii;

int n, m, k, seg[MAXN], sol[MAXN], sag[MAXN], kok[MAXN];
vector < int > g[MAXN];

int up(int k, int bas, int son, int x){
	if(bas > x or son < x)
		return k;
	int yeni = ++m;
	seg[yeni] = seg[k] + 1;
	if(bas == son)
		return yeni;
	sol[yeni] = up(sol[k], bas, orta, x);
	sag[yeni] = up(sag[k], orta + 1, son, x);
	return yeni;
}

int qu(int a, int b, int bas, int son, int x, int y){
	if(bas > y or son < x)
		return 0;
	if(bas >= x and son <= y)
		return seg[b] - seg[a];
	return qu(sol[a], sol[b], bas, orta, x, y) + qu(sag[a], sag[b], orta + 1, son, x, y);
}

ii bs(int a, int b, int bas, int son, int x){
	if(bas == son)
		return mp(bas, seg[b] - seg[a] - x);
	if(seg[sol[b]] - seg[sol[a]] < x)
		return bs(sag[a], sag[b], orta + 1, son, x - (seg[sol[b]] - seg[sol[a]]));
	return bs(sol[a], sol[b], bas, orta, x);
}

void init(int nn, int A[], int B[]) {n = nn;
	for(int i = 0; i < n; i++)
		g[A[i]].pb(B[i]);
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < g[i].size(); j++)
			k = up(k, 1, n, g[i][j]);
		kok[i] = k;
	}
}

int can(int m, int k[]) {
	sort(k, k + m);
	stack < pair < ii , int > > s;
	s.push(mp(mp(inf, 0), 0));
	for(int i = 0; i < m; i++){
		int x = k[i], ara = k[i], alt = k[i], gel, fl = 0;
		while(!s.empty() and s.top().st.st < x){
			s.pop();
			// cout << "Cikti" << endl;
		}
		while((int)s.size() > 1){
			gel = s.top().nd;
			int ne = qu(kok[gel], kok[x], 1, n, alt, s.top().st.st);
			// cout << ne << " -> ";
			if(ne <= ara)
				ara -= ne;
			else
				break;
			if(s.top().st.nd >= ara){
				s.top().st.nd -= ara;
				s.top().nd = x;
				fl = 1;
				break;
			}
			ara -= s.top().st.nd;
			alt = s.top().st.st + 1;
			s.pop();
			// cout << "Cikti 2 " << ara << endl;
		}
		if(fl)
			continue;
		gel = s.top().nd;
		ii y = bs(kok[gel], kok[x], 1, n, ara + qu(kok[gel], kok[x], 1, n, 1, alt - 1));
		// cout << x << " " << gel << " " << s.top().st.st << " " << y.st << " " << y.nd << endl;
		if(y.nd < 0)
			return 0;
		if(y.st == s.top().st.st){
			s.top().st.nd += y.nd;
			s.top().nd = x;
		} else{
			s.push(mp(y, x));
			// cout << "geldi " << s.top().st.st << " " << s.top().st.nd << " " << s.top().nd << endl;
		}
	}
	return 1;
}

Compilation message

teams.cpp: In function 'int up(int, int, int, int)':
teams.cpp:20:38: warning: declaration of 'k' shadows a global declaration [-Wshadow]
 int up(int k, int bas, int son, int x){
                                      ^
teams.cpp:17:11: note: shadowed declaration is here
 int n, m, k, seg[MAXN], sol[MAXN], sag[MAXN], kok[MAXN];
           ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < g[i].size(); j++)
                  ~~^~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:58:23: warning: declaration of 'k' shadows a global declaration [-Wshadow]
 int can(int m, int k[]) {
                       ^
teams.cpp:17:11: note: shadowed declaration is here
 int n, m, k, seg[MAXN], sol[MAXN], sag[MAXN], kok[MAXN];
           ^
teams.cpp:58:23: warning: declaration of 'm' shadows a global declaration [-Wshadow]
 int can(int m, int k[]) {
                       ^
teams.cpp:17:8: note: shadowed declaration is here
 int n, m, k, seg[MAXN], sol[MAXN], sag[MAXN], kok[MAXN];
        ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 235252 KB Output is correct
2 Correct 225 ms 235308 KB Output is correct
3 Correct 214 ms 235128 KB Output is correct
4 Correct 236 ms 235228 KB Output is correct
5 Correct 216 ms 235128 KB Output is correct
6 Correct 257 ms 235256 KB Output is correct
7 Correct 217 ms 235128 KB Output is correct
8 Correct 217 ms 235256 KB Output is correct
9 Correct 219 ms 235172 KB Output is correct
10 Correct 214 ms 235284 KB Output is correct
11 Correct 214 ms 235108 KB Output is correct
12 Correct 220 ms 235256 KB Output is correct
13 Correct 222 ms 235344 KB Output is correct
14 Correct 214 ms 235312 KB Output is correct
15 Correct 214 ms 235164 KB Output is correct
16 Correct 219 ms 235260 KB Output is correct
17 Correct 217 ms 235144 KB Output is correct
18 Correct 219 ms 235176 KB Output is correct
19 Correct 218 ms 235232 KB Output is correct
20 Correct 259 ms 235200 KB Output is correct
21 Correct 250 ms 235348 KB Output is correct
22 Correct 215 ms 235196 KB Output is correct
23 Correct 216 ms 235244 KB Output is correct
24 Correct 216 ms 235128 KB Output is correct
25 Correct 215 ms 235132 KB Output is correct
26 Correct 214 ms 235128 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 260028 KB Output is correct
2 Correct 291 ms 260132 KB Output is correct
3 Correct 293 ms 260212 KB Output is correct
4 Correct 307 ms 260732 KB Output is correct
5 Correct 254 ms 258552 KB Output is correct
6 Correct 259 ms 258572 KB Output is correct
7 Correct 259 ms 258552 KB Output is correct
8 Correct 253 ms 258552 KB Output is correct
9 Correct 279 ms 257644 KB Output is correct
10 Correct 254 ms 257456 KB Output is correct
11 Correct 253 ms 258672 KB Output is correct
12 Correct 252 ms 257560 KB Output is correct
13 Correct 264 ms 259160 KB Output is correct
14 Correct 270 ms 258568 KB Output is correct
15 Correct 288 ms 259960 KB Output is correct
16 Correct 282 ms 259960 KB Output is correct
17 Correct 258 ms 259152 KB Output is correct
18 Correct 259 ms 259284 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 260828 KB Output is correct
2 Correct 299 ms 260708 KB Output is correct
3 Correct 473 ms 263884 KB Output is correct
4 Correct 300 ms 260776 KB Output is correct
5 Correct 290 ms 259212 KB Output is correct
6 Correct 286 ms 259312 KB Output is correct
7 Correct 262 ms 259236 KB Output is correct
8 Correct 280 ms 259312 KB Output is correct
9 Correct 260 ms 257776 KB Output is correct
10 Correct 269 ms 257904 KB Output is correct
11 Correct 277 ms 259276 KB Output is correct
12 Correct 287 ms 258332 KB Output is correct
13 Correct 365 ms 260096 KB Output is correct
14 Correct 476 ms 262364 KB Output is correct
15 Correct 318 ms 260800 KB Output is correct
16 Correct 316 ms 260856 KB Output is correct
17 Correct 287 ms 259880 KB Output is correct
18 Correct 285 ms 259932 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 852 ms 369220 KB Output is correct
2 Correct 881 ms 369432 KB Output is correct
3 Correct 1352 ms 375284 KB Output is correct
4 Correct 819 ms 375032 KB Output is correct
5 Correct 534 ms 366592 KB Output is correct
6 Correct 520 ms 366644 KB Output is correct
7 Correct 450 ms 366488 KB Output is correct
8 Correct 507 ms 366440 KB Output is correct
9 Correct 451 ms 359952 KB Output is correct
10 Correct 475 ms 364336 KB Output is correct
11 Correct 489 ms 364872 KB Output is correct
12 Correct 547 ms 365812 KB Output is correct
13 Correct 879 ms 369216 KB Output is correct
14 Correct 1590 ms 376932 KB Output is correct
15 Correct 756 ms 373852 KB Output is correct
16 Correct 867 ms 373880 KB Output is correct
17 Correct 583 ms 368368 KB Output is correct
18 Correct 529 ms 368252 KB Output is correct