oj.uz

Submission #956824

# Submission time Handle Problem Language Result Execution time Memory
956824 2024-04-02T14:09:59 Z tosivanmak Teams (IOI15_teams) C++17
100 / 100
 3731 ms 484168 KB 
// #pragma GCC optimize("Ofast,unroll-loops,inline")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#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;
    inline 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);
    }
    inline 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);
        }
    }
    inline 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]);
        }
    }
    inline 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);
        }
    }
    inline 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);
    }
    inline 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);
    }
    inline 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]];
    }
    inline 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);
}

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]],1,l,1,n,1)-st.qry(curver,1,l,1,n,1)-ext;
        ll rem=val-k[i];
        if(rem==0){
            st.pre(members[k[i]],1,l,1,n,1);
            st.assign(curver,1,l,1,n,1);
            curver=st.seg[1].size()-1;
        }
        else{
            if(k[i]<=l-1){
            st.pre(members[k[i]],1,l-1,1,n,1);
            st.assign(curver,1,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;
}

// int main() {
//     ios::sync_with_stdio(0);
//     cin.tie(0); cout.tie(0);
// 	// _inputFile = fopen("teams.in", "rb");
// 	// _outputFile = fopen("teams.out", "w");
//     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;
// }

Compilation message

teams.cpp: In member function 'void SEG::init(int)':
teams.cpp:14:25: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   14 |     inline void init(ll n){
      |                         ^
teams.cpp:8:4: note: shadowed declaration is here
    8 | ll n;
      |    ^
teams.cpp: In member function 'void SEG::upd(int, int, int, int, int, int)':
teams.cpp:39: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]
   39 |             lc[id].pb(seg[id*2].size()-1);
      |                       ~~~~~~~~~~~~~~~~^~
teams.cpp:45: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]
   45 |             rc[id].pb(seg[id*2+1].size()-1);
      |                       ~~~~~~~~~~~~~~~~~~^~
teams.cpp: In member function 'void SEG::create(int, int, int)':
teams.cpp:56: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]
   56 |             seg[id].pb(0),lc[id].pb(seg[id*2].size()-1),rc[id].pb(seg[id*2+1].size()-1);
      |                                     ~~~~~~~~~~~~~~~~^~
teams.cpp:56: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]
   56 |             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:98: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]
   98 |             lc[id][seg[id].size()-1]=seg[id*2].size()-1;
      |                                      ~~~~~~~~~~~~~~~~^~
teams.cpp:105: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]
  105 |             rc[id][seg[id].size()-1]=seg[id*2+1].size()-1;
      |                                      ~~~~~~~~~~~~~~~~~~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:171:36: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  171 |             curver=st.seg[1].size()-1;
      |                    ~~~~~~~~~~~~~~~~^~
teams.cpp:177:36: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  177 |             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:160:19: warning: unused variable 'r' [-Wunused-variable]
  160 |         ll l=k[i],r=n;
      |                   ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 4 ms 13148 KB Output is correct
3 Correct 4 ms 13148 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 3 ms 12888 KB Output is correct
7 Correct 3 ms 13144 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 4 ms 13148 KB Output is correct
14 Correct 3 ms 13148 KB Output is correct
15 Correct 3 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 12892 KB Output is correct
19 Correct 3 ms 12912 KB Output is correct
20 Correct 3 ms 12888 KB Output is correct
21 Correct 4 ms 12892 KB Output is correct
22 Correct 3 ms 12892 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 12888 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 282 ms 88244 KB Output is correct
2 Correct 261 ms 88008 KB Output is correct
3 Correct 273 ms 88008 KB Output is correct
4 Correct 268 ms 88356 KB Output is correct
5 Correct 98 ms 83772 KB Output is correct
6 Correct 98 ms 83512 KB Output is correct
7 Correct 101 ms 83512 KB Output is correct
8 Correct 100 ms 83804 KB Output is correct
9 Correct 173 ms 106308 KB Output is correct
10 Correct 132 ms 90016 KB Output is correct
11 Correct 99 ms 85256 KB Output is correct
12 Correct 94 ms 83404 KB Output is correct
13 Correct 110 ms 84312 KB Output is correct
14 Correct 159 ms 88012 KB Output is correct
15 Correct 233 ms 88380 KB Output is correct
16 Correct 237 ms 88120 KB Output is correct
17 Correct 101 ms 84116 KB Output is correct
18 Correct 102 ms 83144 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 88684 KB Output is correct
2 Correct 282 ms 89096 KB Output is correct
3 Correct 707 ms 111892 KB Output is correct
4 Correct 264 ms 88620 KB Output is correct
5 Correct 284 ms 110272 KB Output is correct
6 Correct 274 ms 106888 KB Output is correct
7 Correct 102 ms 84504 KB Output is correct
8 Correct 225 ms 100804 KB Output is correct
9 Correct 182 ms 106592 KB Output is correct
10 Correct 289 ms 122428 KB Output is correct
11 Correct 307 ms 127112 KB Output is correct
12 Correct 294 ms 132396 KB Output is correct
13 Correct 520 ms 127104 KB Output is correct
14 Correct 826 ms 122560 KB Output is correct
15 Correct 348 ms 122876 KB Output is correct
16 Correct 366 ms 124420 KB Output is correct
17 Correct 239 ms 109280 KB Output is correct
18 Correct 240 ms 119932 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2145 ms 402996 KB Output is correct
2 Correct 2186 ms 402448 KB Output is correct
3 Correct 3628 ms 457372 KB Output is correct
4 Correct 2280 ms 403888 KB Output is correct
5 Correct 1124 ms 440524 KB Output is correct
6 Correct 1111 ms 451668 KB Output is correct
7 Correct 600 ms 377508 KB Output is correct
8 Correct 1056 ms 423504 KB Output is correct
9 Correct 1104 ms 484168 KB Output is correct
10 Correct 1093 ms 465444 KB Output is correct
11 Correct 1046 ms 469044 KB Output is correct
12 Correct 1274 ms 476220 KB Output is correct
13 Correct 2266 ms 479288 KB Output is correct
14 Correct 3731 ms 475064 KB Output is correct
15 Correct 1929 ms 480648 KB Output is correct
16 Correct 2044 ms 477456 KB Output is correct
17 Correct 1125 ms 460804 KB Output is correct
18 Correct 1125 ms 450040 KB Output is correct