oj.uz

Submission #596156

# Submission time Handle Problem Language Result Execution time Memory
596156 2022-07-14T12:39:32 Z alirezasamimi100 Teams (IOI15_teams) C++17
100 / 100
 1560 ms 503732 KB 
#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 320 KB Output is correct
20 Correct 1 ms 316 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 67144 KB Output is correct
2 Correct 138 ms 67204 KB Output is correct
3 Correct 119 ms 67188 KB Output is correct
4 Correct 120 ms 67436 KB Output is correct
5 Correct 89 ms 68452 KB Output is correct
6 Correct 89 ms 68112 KB Output is correct
7 Correct 102 ms 67144 KB Output is correct
8 Correct 112 ms 67076 KB Output is correct
9 Correct 140 ms 84580 KB Output is correct
10 Correct 99 ms 72140 KB Output is correct
11 Correct 90 ms 69016 KB Output is correct
12 Correct 106 ms 67992 KB Output is correct
13 Correct 100 ms 67336 KB Output is correct
14 Correct 95 ms 67100 KB Output is correct
15 Correct 119 ms 67220 KB Output is correct
16 Correct 118 ms 67136 KB Output is correct
17 Correct 93 ms 67436 KB Output is correct
18 Correct 91 ms 67380 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 67476 KB Output is correct
2 Correct 138 ms 67608 KB Output is correct
3 Correct 408 ms 71496 KB Output is correct
4 Correct 131 ms 67780 KB Output is correct
5 Correct 202 ms 68888 KB Output is correct
6 Correct 183 ms 68804 KB Output is correct
7 Correct 94 ms 67756 KB Output is correct
8 Correct 161 ms 68832 KB Output is correct
9 Correct 142 ms 84788 KB Output is correct
10 Correct 177 ms 72308 KB Output is correct
11 Correct 187 ms 69244 KB Output is correct
12 Correct 256 ms 68864 KB Output is correct
13 Correct 368 ms 68860 KB Output is correct
14 Correct 435 ms 70256 KB Output is correct
15 Correct 174 ms 68104 KB Output is correct
16 Correct 186 ms 68008 KB Output is correct
17 Correct 181 ms 68124 KB Output is correct
18 Correct 157 ms 69456 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 805 ms 368604 KB Output is correct
2 Correct 785 ms 368688 KB Output is correct
3 Correct 1522 ms 378576 KB Output is correct
4 Correct 777 ms 368808 KB Output is correct
5 Correct 991 ms 372904 KB Output is correct
6 Correct 849 ms 372928 KB Output is correct
7 Correct 486 ms 368908 KB Output is correct
8 Correct 769 ms 372924 KB Output is correct
9 Correct 783 ms 503732 KB Output is correct
10 Correct 669 ms 376036 KB Output is correct
11 Correct 823 ms 373744 KB Output is correct
12 Correct 943 ms 372912 KB Output is correct
13 Correct 1304 ms 372972 KB Output is correct
14 Correct 1560 ms 375772 KB Output is correct
15 Correct 786 ms 369368 KB Output is correct
16 Correct 801 ms 376568 KB Output is correct
17 Correct 646 ms 376112 KB Output is correct
18 Correct 634 ms 376308 KB Output is correct