oj.uz

Submission #956811

# Submission time Handle Problem Language Result Execution time Memory
956811 2024-04-02T13:40:59 Z tosivanmak Teams (IOI15_teams) C++17
77 / 100
 3860 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back

ll n; 
ll refseg=1,curver;
ll members[500005];
struct SEG{
    vector<vector<ll> >seg,lc,rc;
    vector<ll>temp,templ,tempr;
    void init(ll n){
        seg.resize(4*n+5),lc.resize(4*n+5),rc.resize(4*n+5),temp.resize(4*n+5);
        templ.resize(4*n+5),tempr.resize(4*n+5);
    }
    void build(ll l, ll r, ll id){
        if(l==r){
            seg[id].pb(0);
            return;
        }
        else{
            ll mid=(l+r)>>1;
            build(l,mid,id*2),build(mid+1,r,id*2+1);
            seg[id].pb(0),lc[id].pb(0),rc[id].pb(0);
        }
    }
    void upd(ll ver, ll ul, ll l, ll r, ll val, ll id){
        // cout<<ver<<' '<<ul<<' '<<l<<" "<<r<<" "<<val<<" "<<id<<'\n';
        if(l==r){
            seg[id].pb(seg[id][ver]+val);
            return;
        }
        ll mid=(l+r)>>1;
        if(ul<=mid){
            upd(lc[id][ver],ul,l,mid,val,id*2);
            seg[id].pb(seg[id][ver]+val);
            lc[id].pb(seg[id*2].size()-1);
            rc[id].pb(rc[id][ver]);
        }
        else{
            upd(rc[id][ver],ul,mid+1,r,val,id*2+1);
            seg[id].pb(seg[id][ver]+val);
            rc[id].pb(seg[id*2+1].size()-1);
            lc[id].pb(lc[id][ver]);
        }
    }
    void create(ll l, ll r, ll id){
        if(l==r){
            seg[id].pb(0);
        }
        else{
            ll mid=(l+r)>>1;
            create(l,mid,id*2),create(mid+1,r,id*2+1);
            seg[id].pb(0),lc[id].pb(seg[id*2].size()-1),rc[id].pb(seg[id*2+1].size()-1);
        }
    }
    void pre(ll ver, ll ql, ll qr, ll l, ll r, ll id){
        if(l>qr||r<ql||ql>qr){
            return;
        }
        if(l>=ql&&r<=qr){
            temp[id]=ver;
            if(l!=r){templ[id]=lc[id][ver],tempr[id]=rc[id][ver];}
            return;
        }
        ll mid=(l+r)>>1;
        pre(lc[id][ver],ql,qr,l,mid,id*2),pre(rc[id][ver],ql,qr,mid+1,r,id*2+1);
    }
    ll qry(ll ver, ll ql, ll qr, ll l, ll r, ll id){
        if(l>qr||r<ql){
            return 0;
        }
        if(l>=ql&&r<=qr){ 
            return seg[id][ver];
        }
        ll mid=(l+r)>>1;
        return qry(lc[id][ver],ql,qr,l,mid,id*2)+qry(rc[id][ver],ql,qr,mid+1,r,id*2+1);
    }
    void assign(ll ver, ll ql, ll qr, ll l, ll r, ll id){
        if(l>qr||r<ql||ql>qr){
            return;
        }
        seg[id].pb(0);
        if(l>=ql&&r<=qr){
            if(l!=r){
                lc[id].pb(templ[id]);
                rc[id].pb(tempr[id]);
            }
            seg[id][seg[id].size()-1]=seg[id][temp[id]];
            return;
        }
        lc[id].pb(0),rc[id].pb(0);
        ll mid=(l+r)>>1;
        if(mid>=ql){
            assign(lc[id][ver],ql,qr,l,mid,id*2);
            lc[id][seg[id].size()-1]=seg[id*2].size()-1;
        }
        else{
            lc[id][seg[id].size()-1]=lc[id][ver];
        }
        if(mid+1<=qr){
            assign(rc[id][ver],ql,qr,mid+1,r,id*2+1);
            rc[id][seg[id].size()-1]=seg[id*2+1].size()-1;
        }
        else{
            rc[id][seg[id].size()-1]=rc[id][ver];
        }
        seg[id][seg[id].size()-1]=seg[id*2][lc[id][seg[id].size()-1]]+seg[id*2+1][rc[id][seg[id].size()-1]];
    }
    ll bs(ll ver1, ll ver2, ll l, ll r, ll val, ll id){
        if(seg[id][ver1]-seg[id][ver2]<val){return -1;}
        if(l==r){
            return l;
        }
        ll mid=(l+r)>>1;
        if(seg[id*2][lc[id][ver1]]-seg[id*2][lc[id][ver2]]>=val){
           return bs(lc[id][ver1],lc[id][ver2],l,mid,val,id*2);
        }
        else{
            return bs(rc[id][ver1],rc[id][ver2],mid+1,r,val-(seg[id*2][lc[id][ver1]]-seg[id*2][lc[id][ver2]]),id*2+1);
        }
    }
}st;
vector<ll>adj[500005];
void init(int N, int a[], int b[]) {
    n=N;
   for(int i=0;i<n;i++){
       adj[a[i]].pb(b[i]);
   }
   st.init(n); st.build(1,n,1);
   for(int i=1;i<=n;i++){
       for(auto& u: adj[i]){
        //    cout<<u<<" ";
           st.upd(refseg-1,u,1,n,1,1);
        //    st.upd(refseg-1,u,1,n,1,1);
           refseg++;
       }
       members[i]=refseg-1;
   }
//    cout<<members[1]<<'\n';
    // cout<<st.qry(4,2,4,1,n,1)<<'\n';
    
   st.create(1,n,1);
}


bool ck(ll used, ll cur, ll par){
    ll hv=st.qry(members[cur],cur,par,1,n,1);
    ll alr=st.qry(used,cur,par,1,n,1);
    return (hv-alr)>=cur;
}
int can(int m, int k[]) {
    ll sum=0;
    for(int i=0;i<m;i++){
        sum+=k[i];
    }
    if(sum>n){
        return 0;
    }
    curver=n+1;
    sort(k,k+m);
    for(int i=0;i<m;i++){
        // cout<<k[i]<<" "<<curver<<'\n';
        ll l=k[i],r=n;
        // if(!ck(curver,k[i],r))return 0;
        ll ext=st.qry(members[k[i]],1,k[i]-1,1,n,1)-st.qry(curver,1,k[i]-1,1,n,1);
        l=st.bs(members[k[i]],curver,1,n,k[i]+ext,1);
        if(l==-1)return 0;
        ll lol2=st.qry(members[k[i]],l,l,1,n,1);
        ll val=st.qry(members[k[i]],k[i],l,1,n,1)-st.qry(curver,k[i],l,1,n,1);
        ll rem=val-k[i];
        if(rem==0){
            st.pre(members[k[i]],k[i],l,1,n,1);
            st.assign(curver,k[i],l,1,n,1);
            curver=st.seg[1].size()-1;
        }
        else{
            if(k[i]<=l-1){
            st.pre(members[k[i]],k[i],l-1,1,n,1);
            st.assign(curver,k[i],l-1,1,n,1);
            curver=st.seg[1].size()-1;
            }
            ll lol=st.qry(curver,l,l,1,n,1);
            st.upd(curver,l,1,n,lol2-rem-lol,1);
            curver=st.seg[1].size()-1;
        }
    }
    return 1;
}

Compilation message

teams.cpp: In member function 'void SEG::init(int)':
teams.cpp:12:18: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   12 |     void init(ll n){
      |                  ^
teams.cpp:6:4: note: shadowed declaration is here
    6 | ll n;
      |    ^
teams.cpp: In member function 'void SEG::upd(int, int, int, int, int, int)':
teams.cpp:37:39: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
   37 |             lc[id].pb(seg[id*2].size()-1);
      |                       ~~~~~~~~~~~~~~~~^~
teams.cpp:43:41: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
   43 |             rc[id].pb(seg[id*2+1].size()-1);
      |                       ~~~~~~~~~~~~~~~~~~^~
teams.cpp: In member function 'void SEG::create(int, int, int)':
teams.cpp:54:53: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
   54 |             seg[id].pb(0),lc[id].pb(seg[id*2].size()-1),rc[id].pb(seg[id*2+1].size()-1);
      |                                     ~~~~~~~~~~~~~~~~^~
teams.cpp:54:85: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
   54 |             seg[id].pb(0),lc[id].pb(seg[id*2].size()-1),rc[id].pb(seg[id*2+1].size()-1);
      |                                                                   ~~~~~~~~~~~~~~~~~~^~
teams.cpp: In member function 'void SEG::assign(int, int, int, int, int, int)':
teams.cpp:96:54: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   96 |             lc[id][seg[id].size()-1]=seg[id*2].size()-1;
      |                                      ~~~~~~~~~~~~~~~~^~
teams.cpp:103:56: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
  103 |             rc[id][seg[id].size()-1]=seg[id*2+1].size()-1;
      |                                      ~~~~~~~~~~~~~~~~~~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:175:36: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  175 |             curver=st.seg[1].size()-1;
      |                    ~~~~~~~~~~~~~~~~^~
teams.cpp:181:36: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  181 |             curver=st.seg[1].size()-1;
      |                    ~~~~~~~~~~~~~~~~^~
teams.cpp:185:36: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  185 |             curver=st.seg[1].size()-1;
      |                    ~~~~~~~~~~~~~~~~^~
teams.cpp:164:19: warning: unused variable 'r' [-Wunused-variable]
  164 |         ll l=k[i],r=n;
      |                   ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 4 ms 12924 KB Output is correct
7 Correct 3 ms 13148 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 5 ms 13656 KB Output is correct
13 Correct 5 ms 13184 KB Output is correct
14 Correct 3 ms 13148 KB Output is correct
15 Correct 4 ms 12892 KB Output is correct
16 Correct 3 ms 12892 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 3 ms 12888 KB Output is correct
19 Correct 3 ms 12892 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 3 ms 12908 KB Output is correct
22 Correct 3 ms 12888 KB Output is correct
23 Correct 3 ms 12892 KB Output is correct
24 Correct 3 ms 12892 KB Output is correct
25 Correct 3 ms 12892 KB Output is correct
26 Correct 3 ms 12892 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 88144 KB Output is correct
2 Correct 269 ms 88492 KB Output is correct
3 Correct 261 ms 87972 KB Output is correct
4 Correct 265 ms 88376 KB Output is correct
5 Correct 102 ms 83792 KB Output is correct
6 Correct 94 ms 83640 KB Output is correct
7 Correct 91 ms 83728 KB Output is correct
8 Correct 96 ms 83768 KB Output is correct
9 Correct 233 ms 123916 KB Output is correct
10 Correct 131 ms 90012 KB Output is correct
11 Correct 126 ms 85012 KB Output is correct
12 Correct 96 ms 83148 KB Output is correct
13 Correct 112 ms 84056 KB Output is correct
14 Correct 166 ms 87756 KB Output is correct
15 Correct 256 ms 88372 KB Output is correct
16 Correct 225 ms 88116 KB Output is correct
17 Correct 99 ms 84116 KB Output is correct
18 Correct 99 ms 83208 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 88988 KB Output is correct
2 Correct 263 ms 89388 KB Output is correct
3 Correct 882 ms 128916 KB Output is correct
4 Correct 273 ms 88532 KB Output is correct
5 Correct 274 ms 105928 KB Output is correct
6 Correct 250 ms 103360 KB Output is correct
7 Correct 100 ms 84268 KB Output is correct
8 Correct 209 ms 98196 KB Output is correct
9 Correct 233 ms 123520 KB Output is correct
10 Correct 296 ms 126272 KB Output is correct
11 Correct 324 ms 140160 KB Output is correct
12 Correct 363 ms 147240 KB Output is correct
13 Correct 644 ms 150624 KB Output is correct
14 Correct 1002 ms 147204 KB Output is correct
15 Correct 381 ms 129988 KB Output is correct
16 Correct 384 ms 131268 KB Output is correct
17 Correct 232 ms 109940 KB Output is correct
18 Correct 267 ms 123568 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2043 ms 401776 KB Output is correct
2 Correct 2045 ms 398804 KB Output is correct
3 Correct 3860 ms 492152 KB Output is correct
4 Correct 1996 ms 405196 KB Output is correct
5 Correct 1006 ms 428404 KB Output is correct
6 Correct 959 ms 421452 KB Output is correct
7 Correct 559 ms 377524 KB Output is correct
8 Correct 848 ms 415596 KB Output is correct
9 Runtime error 1272 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -