Submission #287410

#	Time	Username	Problem	Language	Result	Execution time	Memory
287410		shayan_p	Teams (IOI15_teams)	C++17	100 / 100	3844 ms	507228 KiB

teams

// Oh damn! Suddenly you're free to fly...
 
#include<bits/stdc++.h>
#include "teams.h"
 
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
 
const int maxn = 5e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10, SQ = 1000;
 
pii p[maxn];
int n;
 
vector<pii> vec[4 * maxn];
vector<int> vecId[4 * maxn];
vector<int> LC[4 * maxn], RC[4 * maxn];
 
bool leaf[4 * maxn];
int used[4 * maxn];
int lazyUsed[4 * maxn];

void shift(int l, int r, int id){
    if(leaf[id] == 0)
	return;
    assert(r-l > 1);
    leaf[id] = 0;
    //    used[id] = 0;
    leaf[2*id] = leaf[2*id+1] = 1;
    used[2*id] = LC[id][ used[id] ];
    used[2*id + 1] = RC[id][ used[id] ];
    lazyUsed[2*id] = used[2*id];
    lazyUsed[2*id+1] = used[2*id+1];
}
void build(int l = 0, int r = n, int id = 1){
    if(r-l == 1){
	vec[id].PB(p[l]);
	vecId[id].PB(l);
	LC[id].PB(-1), RC[id].PB(-1);
	return; // behold LC RC
    }
    int mid = (l+r) >> 1;
    build(l, mid, 2*id);
    build(mid, r, 2*id + 1);
    int pt1 = 0, pt2 = 0;
    while(pt1 < sz(vec[2*id]) || pt2 < sz(vec[2*id+1])){
	LC[id].PB(pt1), RC[id].PB(pt2);
	if(pt2 == sz(vec[2*id+1]) || (pt1 != sz(vec[2*id]) && vec[2*id][pt1].S > vec[2*id+1][pt2].S))
	    vec[id].PB(vec[2*id][pt1]), vecId[id].PB(vecId[2*id][pt1]), pt1++;
	else
	    vec[id].PB(vec[2*id+1][pt2]), vecId[id].PB(vecId[2*id+1][pt2]), pt2++;	    
    }
    LC[id].PB(pt1), RC[id].PB(pt2);
}

bool bad[maxn];
vector<int> clearBad;

inline void isBad(int x){
    if(bad[x])
	return;
    bad[x] = 1;
    clearBad.PB(x);
}

void go(int pos, int &need, int RP = -1, int l = 0, int r = n, int id = 1){
    if(id == 1){
	int f = -1, s = n;
	while(s-f > 1){
	    int mid = (f + s) >> 1;
	    if(vec[id][mid].S >= pos)
		f = mid;
	    else
		s = mid;
	}
	if(s - used[id] < need) //////
	    throw "SHIT";
	RP = s;
    }
    if(need == 0 || RP - used[id] <= 0)
	return;
    if(p[l].F > pos)
	return;
    if(p[r-1].F <= pos && leaf[id]){
	int delta = min(need, RP - used[id]);
	if(delta == RP - used[id]){
	    need-= delta;
	    used[id]+= delta;
	    lazyUsed[id] = used[id];
	    return;
	}
    }
    if(r-l < SQ){
	for(int i = 0; i < lazyUsed[id]; i++)
	    isBad(vecId[id][i]);
	for(int i = r-1; need && i >= l; i--){
	    if(!bad[i] && p[i].F <= pos && pos <= p[i].S)
		isBad(i), --need, used[id]++;
	}
	return;
    }
    
    shift(l, r, id);
    int mid = (l+r) >> 1;
    go(pos, need, RC[id][RP], mid, r, 2*id+1);
    go(pos, need, LC[id][RP], l, mid, 2*id);
}
 
void init(int n, int l[], int r[]){    
    for(int i = 0; i < n; i++)
	p[i] = {l[i], r[i]};
    sort(p, p + n);
    ::n = n;
    build();
}
int can(int m, int a[]){
    for(int x : clearBad){
	bad[x] = 0;	
    }
    clearBad.clear();
    
    leaf[1] = 1;
    used[1] = 0;
    lazyUsed[1] = 0;
    
    sort(a, a + m);
    int need = 0;
    for(int i = m-1; i >= 0; i--){
	need+= a[i];
	if(need > n)
	    return 0;
	if(i == 0 || a[i] != a[i-1]){
	    try{
		go(a[i], need);
		if(need != 0)
		    throw "SHIT2";
	    }
	    catch(...){
		return 0;
	    }
	}
    }
    return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:116:34: warning: declaration of 'n' shadows a global declaration [-Wshadow]
  116 | void init(int n, int l[], int r[]){
      |                                  ^
teams.cpp:20:5: note: shadowed declaration is here
   20 | int n;
      |     ^

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23