Submission #596156

#	Time	Username	Problem	Language	Result	Execution time	Memory
596156		alirezasamimi100	Teams (IOI15_teams)	C++17	100 / 100	1560 ms	503732 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
using pii = pair<int, int>;

const int N = 5e5 + 10, inf = 1.05e9;

int n,f[N*4];
vector<pii> vel,ver;
vector<int> ch;
struct node{
    node *lc,*rc;
    int x;
    node(){
        lc=rc=nullptr;
        x=0;
    }
} *prs[N],*lz[N*4];

node* build(int l, int r){
    node *v = new node;
    if(r-l==1) return v;
    int m=(l+r)>>1;
    v->lc=build(l,m);
    v->rc=build(m,r);
    return v;
}

node* upd(node* v, int l, int r, int p){
    node* ans = new node;
    if(r-l==1){
        ans->x=1;
        return ans;
    }
    int m=(l+r)>>1;
    if(p<m){
        ans->lc=upd(v->lc,l,m,p);
        ans->rc=v->rc;
        ans->x=ans->lc->x+ans->rc->x;
        return ans;
    }
    ans->lc=v->lc;
    ans->rc=upd(v->rc,m,r,p);
    ans->x=ans->lc->x+ans->rc->x;
    return ans;
}

void wtbuild(int v, int l, int r){
    lz[v]=nullptr;
    if(r-l==1) return;
    int m=(l+r)>>1,lc=v<<1,rc=v<<1|1;
    wtbuild(lc,l,m);
    wtbuild(rc,m,r);
}

void shift(int v, int l, int r){
    if(!lz[v]) return;
    f[v]=lz[v]->x;
    if(r-l>1){
        int lc=v<<1,rc=v<<1|1;
        lz[lc]=lz[v]->lc;
        lz[rc]=lz[v]->rc;
        ch.pb(lc);
        ch.pb(rc);
    }
    lz[v]=nullptr;
}

int get(int v, int l, int r, int tl, int tr, int x, node* s){
    ch.pb(v);
    shift(v,l,r);
    if(l>=tr || tl>=r || tl>=tr) return 0;
    if(l>=tl && r<=tr && s->x-f[v]<=x){
        lz[v]=s;
        int k=s->x-f[v];
        shift(v,l,r);
        return k;
    }
    int m=(l+r)>>1;
    int lc=v<<1,rc=v<<1|1;
    int lk=get(lc,l,m,tl,tr,x,s->lc);
    if(lk<x) lk+=get(rc,m,r,tl,tr,x-lk,s->rc);
    else shift(rc,m,r);
    f[v]=f[lc]+f[rc];
    return lk;
}

void init(int N, int A[], int B[]) {
    n=N;
    wtbuild(1,0,n);
    for(int i=0; i<n; i++) ver.pb({B[i],A[i]});
    sort(ver.begin(),ver.end());
    vel.pb({-1,-1});
    for(int i=0; i<n; i++) vel.pb({ver[i].S,i});
    sort(vel.begin(),vel.end());
    prs[0]=build(0,n);
    for(int i=1; i<=n; i++) prs[i]=upd(prs[i-1],0,n,vel[i].S);
}

int can(int M, int K[]) {
    int ans=1;
    sort(K,K+M);
    for(int i=0; i<M; i++){
        int t=lower_bound(vel.begin(),vel.end(),mp(K[i]+1,-1))-vel.begin()-1;
        int k=lower_bound(ver.begin(),ver.end(),mp(K[i],-1))-ver.begin();
        int x=get(1,0,n,k,n,K[i],prs[t]);
        if(x<K[i]){
            ans=0;
            break;
        }
    }
    for(int i : ch){
        f[i]=0;
        lz[i]=nullptr;
    }
    ch.clear();
    return ans;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:92:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   92 | void init(int N, int A[], int B[]) {
      |           ~~~~^
teams.cpp:10:11: note: shadowed declaration is here
   10 | const int N = 5e5 + 10, inf = 1.05e9;
      |           ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:108:75: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  108 |         int t=lower_bound(vel.begin(),vel.end(),mp(K[i]+1,-1))-vel.begin()-1;
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:109:61: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  109 |         int k=lower_bound(ver.begin(),ver.end(),mp(K[i],-1))-ver.begin();
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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