Submission #200239

#	Time	Username	Problem	Language	Result	Execution time	Memory
200239		Mercenary	Teams (IOI15_teams)	C++14	100 / 100	1718 ms	425936 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 , dp[maxn];
vector<int> val[maxn];

struct node{
    int sum , l , r;
    node(int sum , int l , int r):sum(sum),l(l),r(r){};
    node(){};
};
vector<node> data;

int MakeNode(int l , int r){
    data.pb(node(data[l].sum+data[r].sum,l,r));
    return (int)data.size() - 1;
}

int U(int x , int l , int r , int pos){
    if(l == r){
        int cur = MakeNode(0,0);data[cur].sum = data[x].sum + 1;
        return cur;
    }
    int mid = l + r >> 1;
    if(pos <= mid)return MakeNode(U(data[x].l,l,mid,pos),data[x].r);
    return MakeNode(data[x].l,U(data[x].r,mid+1,r,pos));
}

int R(int x , int l , int r , int pos){
    if(l == r)return 0;
    int mid = l + r >> 1;
    if(pos <= mid){
        return MakeNode(R(data[x].l,l,mid,pos),data[x].r);
    }else{
        return MakeNode(0,R(data[x].r,mid+1,r,pos));
    }
}

int Q(int x,int u,int l , int r ,int need){
    if(l == r){
        int cur = MakeNode(0,0);data[cur].sum = data[u].sum + need;
        return cur;
    }
    int mid = l + r >> 1;
    int tmp = data[data[x].l].sum - data[data[u].l].sum;
    if(tmp >= need)return MakeNode(Q(data[x].l,data[u].l,l,mid,need),data[u].r);
    return MakeNode(data[x].l,Q(data[x].r,data[u].r,mid+1,r,need-tmp));
}

void init(int N, int A[], int B[]) {
    n = N;
    for(int i = 0 ; i < n ; ++i){
        val[A[i]].pb(B[i]);
    }
    data.pb(node(0,0,0));
    dp[0] = 0;
    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);
        }
        if(i > 1)dp[i] = R(dp[i],1,n,i-1);
    }
}

int can(int M, int K[]) {
    sort(K , K + M);
    int used = MakeNode(0,0);
    for(int i = 0 ; i < M ; ++i){
        if(K[i] > 1)used = R(used,1,n,K[i]-1);
        if(data[used].sum + K[i] > data[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, int, int)':
teams.cpp:16:34: warning: declaration of 'r' shadows a member of 'node' [-Wshadow]
     node(int sum , int l , int r):sum(sum),l(l),r(r){};
                                  ^
teams.cpp:15:19: note: shadowed declaration is here
     int sum , l , r;
                   ^
teams.cpp:16:34: warning: declaration of 'l' shadows a member of 'node' [-Wshadow]
     node(int sum , int l , int r):sum(sum),l(l),r(r){};
                                  ^
teams.cpp:15:15: note: shadowed declaration is here
     int sum , l , r;
               ^
teams.cpp:16:34: warning: declaration of 'sum' shadows a member of 'node' [-Wshadow]
     node(int sum , int l , int r):sum(sum),l(l),r(r){};
                                  ^
teams.cpp:15:9: note: shadowed declaration is here
     int sum , l , r;
         ^~~
teams.cpp: In function 'int U(int, int, int, int)':
teams.cpp:31:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
teams.cpp: In function 'int R(int, int, int, int)':
teams.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
teams.cpp: In function 'int Q(int, int, int, int, int)':
teams.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:65:13: warning: unused variable 'cnt' [-Wunused-variable]
         int cnt = 0;
             ^~~

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