Submission #1075778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075778		Victor	Teams (IOI15_teams)	C++17	0 / 100	721 ms	524288 KiB

teams

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include "teams.h"

using namespace std;

#define rep(i, a, b) for (ll i = (a); i < (b); ++i)
#define per(i, a, b) for (ll i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) (ll) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> ppll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vll> vvll;

const ll INF = 1'000'000'007;

struct persNode {
    ll lo,hi,sum=0;
    persNode *l,*r;

    persNode(ll L, ll R) : lo(L),hi(R) {
        if(hi-lo!=1) {
            ll mid=(lo+hi)/2;
            l=new persNode(lo,mid);
            r=new persNode(mid,hi);
        } 
    }

    persNode(persNode *root,ll pos) {
        lo=root->lo;
        hi=root->hi;

        if(hi-lo==1) {
            sum=root->sum+1;

        } else {
            ll mid=(lo+hi)/2;
            
            if(pos<mid) {
                l=new persNode(root->l,pos);
                r=root->r;

            } else {
                l=root->l;
                r=new persNode(root->r,pos);
            }

            sum=l->sum+r->sum;
        }
    }

    ll query(ll L,ll R) {
        if(hi<=L||R<=lo) return 0;
        if(L<=lo&&hi<=R) return sum;

        return l->query(L,R)+r->query(L,R);
    }
};

struct Node {
    ll lo,hi,sum=0;
    Node *l,*r;
    Node(ll L,ll R) : lo(L),hi(R) {
        if(hi-lo!=1) {
            ll mid=(lo+hi)/2;
            l=new Node(lo,mid);
            r=new Node(mid,hi);
        }
    }

    void update(ll pos,ll x) {
        if(pos<lo||hi<=pos) return;
        if(hi-lo==1) {
            sum+=x;
            return;
        }
        l->update(pos,x);
        r->update(pos,x);
        sum+=x;
    }

    ll query(ll L,ll R) {
        if(hi<=L||R<=lo) return 0;
        if(L<=lo&&hi<=R) return sum;

        return l->query(L,R)+r->query(L,R);
    }

    ll walk(persNode *PersNode,ll target,ll L) {
        if(hi-lo==1) return lo;
        //cout<<"lo = "<<lo<<" hi = "<<hi<<" pers->l = "<<PersNode->l->sum<<" query = "<<query(L,hi)<<" sum = "<<sum<<" target = "<<target<<endl;
        if(PersNode->l->sum<target+query(L,hi)) return r->walk(PersNode->r,target-PersNode->l->sum+l->query(L,hi),L);
        else return l->walk(PersNode->l,target+r->query(L,hi),L);
    }
};


vector<persNode *> perstree;
ll n;
vpll people;
vll sizetotree;
Node *segtree;

const ll segsize=800'000;

void init(int N, int A[], int B[]) {
    //cout<<1<<endl;
    n=N;
    rep(i,0,n) people.emplace_back(A[i],B[i]);

    sort(all(people));
    perstree.pb(new persNode(0LL,segsize));

    //cout<<2<<endl;r
    ll j=0;
    rep(i,0,n+1) {
        while(j<n&&people[j].first==i) perstree.pb(new persNode(perstree[j],people[j].second)),++j;
        sizetotree.pb(j);
    }
    //cout<<3<<endl;
}

int can(int M, int K[]) {
    segtree=new Node(0,segsize);
    sort(K,K+M);
    rep(i,0,M) {
        ll siz=K[i];
        ll persid=sizetotree[siz];
        ll rem=perstree[persid]->query(0,siz);
        
        ll pos=segtree->walk(perstree[persid],siz+rem,siz);
        if(pos==2*n) return 0;

        segtree->update(pos,siz);
        //cout<<"persid = "<<persid<<" i = "<<i<<" siz = "<<siz<<" pos = "<<pos<<" rem = "<<rem<<endl<<endl;
    }
    return 1;
}

/**
#include <stdio.h>
#include <stdlib.h>


static char buffer[1024];
static int currentChar = 0;
static int charsNumber = 0;

static inline int read() {
    if (charsNumber < 0) {
        exit(1);
    }
    if (!charsNumber || currentChar == charsNumber) {
        charsNumber = (int)fread(buffer, sizeof(buffer[0]), sizeof(buffer), stdin);
        currentChar = 0;
    }
    if (charsNumber <= 0) {
        return -1;
    }
    return buffer[currentChar++];
}

static inline int readInt() {
    int c, x, s;
    c = read();
    while (c <= 32)
        c = read();
    x = 0;
    s = 1;
    if (c == '-') {
        s = -1;
        c = read();
    }
    while (c > 32) {
        x *= 10;
        x += c - '0';
        c = read();
    }
    if (s < 0)
        x = -x;
    return x;
}

int main() {
    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];
        cin>>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];
        }
        fprintf(stdout, "%d\n", can(M, K));
    }
    fflush(stdout);
    _Exit(0);
    return 0;
}/**/

Compilation message (stderr)

teams.cpp:227:2: warning: "/*" within comment [-Wcomment]
  227 | }/**/
      |

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