Submission #200222

#	Time	Username	Problem	Language	Result	Execution time	Memory
200222		Mercenary	Teams (IOI15_teams)	C++14	77 / 100	1448 ms	524292 KiB

teams

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> ii;

#ifndef LOCAL
#include "teams.h"
#endif // LOCAL
const int maxn = 5e5 + 5;
int n;
vector<int> val[maxn];

struct node{
    int sum;
    node*l ,*r;
    node(int sum , node*l , node*r):sum(sum),l(l),r(r){};
    node(){};
};

node*Nul;

node* dp[maxn];

node* U(node * x , int l , int r , int pos , int val){
    node * it = new node(x->sum,x->l,x->r);
    if(l == r){
        it->sum += val;
        return it;
    }
    int mid = l + r >> 1;
    if(mid >= pos)it->l = U(it->l,l,mid,pos,val);
    else it->r = U(it->r,mid+1,r,pos,val);
    it->sum = it->l->sum + it->r->sum;
    return it;
}

node * R(node * x , int l , int r , int pos){
    if(l == r)return Nul;
    int mid = l + r >> 1;
    node * it = new node();
    if(pos <= mid){
        it->l = R(x->l,l,mid,pos);
        it->r = x->r;
    }else{
        it->l = Nul;
        it->r = R(x->r,mid+1,r,pos);
    }
    it->sum = it->l->sum + it->r->sum;
    return it;
}

node* Q(node*x,node*u,int l , int r ,int need){
    if(l == r){
        return new node(u->sum+need,Nul,Nul);
    }
    int mid = l + r >> 1;
    node * it = new node;
    if(x->l->sum - u->l->sum >= need){
        it->l = Q(x->l,u->l,l,mid,need);
        it->r = u->r;
    }else{
        it->l = x->l;
        it->r = Q(x->r,u->r,mid+1,r,need - (x->l->sum - u->l->sum));
    }
    it->sum = it->l->sum + it->r->sum;
    return it;
}

void init(int N, int A[], int B[]) {
    n = N;
    for(int i = 0 ; i < n ; ++i){
        val[A[i]].pb(B[i]);
    }
    Nul = new node(0,0,0);Nul->l = Nul->r = Nul;
    dp[0] = Nul;
    for(int i = 1 ; i <= n ; ++i){
        int cnt = 0;
        dp[i] = dp[i - 1];
        for(auto &c : val[i]){
            dp[i] = U(dp[i],1,n,c,1);
        }
        if(i > 1)dp[i] = R(dp[i],1,n,i-1);
    }
}

int can(int M, int K[]) {
    sort(K , K + M);
    node * used = new node(0,Nul,Nul);
    for(int i = 0 ; i < M ; ++i){
        if(K[i] > 1)used = R(used,1,n,K[i]-1);
        if(used->sum + K[i] > dp[K[i]]->sum)return 0;
        used = Q(dp[K[i]],used,1,n,K[i]);
    }
    return 1;
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen("a.inp", "r")) {
        freopen("a.inp", "r", stdin);
        freopen("a.out", "w", stdout);
    }
    int N;
    cin >> N;
    int *A = (int*)malloc(sizeof(int)*(unsigned int)N);
    int *B = (int*)malloc(sizeof(int)*(unsigned int)N);
    for (int i = 0; i < N; ++i) {
    	cin >> A[i] >> B[i];
    }
    init(N, A, B);
    int Q;cin >> Q;
    for (int i = 0; i < Q; ++i) {
    	int M;cin >> M;
	int *K = (int*)malloc(sizeof(int)*(unsigned int)M);
    	for (int j = 0; j < M; ++j) {
            cin >> K[j];
    	}
        cout << can(M,K) << '\n';
    }
    return 0;

}
#endif // LOCAL

Compilation message (stderr)

teams.cpp: In constructor 'node::node(int, node*, node*)':
teams.cpp:17:36: warning: declaration of 'r' shadows a member of 'node' [-Wshadow]
     node(int sum , node*l , node*r):sum(sum),l(l),r(r){};
                                    ^
teams.cpp:16:14: note: shadowed declaration is here
     node*l ,*r;
              ^
teams.cpp:17:36: warning: declaration of 'l' shadows a member of 'node' [-Wshadow]
     node(int sum , node*l , node*r):sum(sum),l(l),r(r){};
                                    ^
teams.cpp:16:10: note: shadowed declaration is here
     node*l ,*r;
          ^
teams.cpp:17:36: warning: declaration of 'sum' shadows a member of 'node' [-Wshadow]
     node(int sum , node*l , node*r):sum(sum),l(l),r(r){};
                                    ^
teams.cpp:15:9: note: shadowed declaration is here
     int sum;
         ^~~
teams.cpp: In function 'node* U(node*, int, int, int, int)':
teams.cpp:25:53: warning: declaration of 'val' shadows a global declaration [-Wshadow]
 node* U(node * x , int l , int r , int pos , int val){
                                                     ^
teams.cpp:12:13: note: shadowed declaration is here
 vector<int> val[maxn];
             ^~~
teams.cpp:31:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
teams.cpp: In function 'node* R(node*, int, int, int)':
teams.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
teams.cpp: In function 'node* Q(node*, node*, int, int, int)':
teams.cpp:57:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:78:13: warning: unused variable 'cnt' [-Wunused-variable]
         int cnt = 0;
             ^~~

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