Submission #127468

#	Time	Username	Problem	Language	Result	Execution time	Memory
127468		ekrem	Teams (IOI15_teams)	C++98	21 / 100	911 ms	57080 KiB

teams

#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 1000005
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 (stderr)

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 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23