oj.uz

Submission #956825

# Submission time Handle Problem Language Result Execution time Memory
956825 2024-04-02T14:10:17 Z tosivanmak Teams (IOI15_teams) C++17
100 / 100
 3921 ms 484144 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 12892 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 3 ms 13144 KB Output is correct
6 Correct 3 ms 12892 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 12888 KB Output is correct
12 Correct 5 ms 13464 KB Output is correct
13 Correct 4 ms 13144 KB Output is correct
14 Correct 3 ms 13144 KB Output is correct
15 Correct 6 ms 13048 KB Output is correct
16 Correct 4 ms 12892 KB Output is correct
17 Correct 5 ms 12892 KB Output is correct
18 Correct 4 ms 12892 KB Output is correct
19 Correct 5 ms 12892 KB Output is correct
20 Correct 4 ms 12892 KB Output is correct
21 Correct 4 ms 12896 KB Output is correct
22 Correct 5 ms 12888 KB Output is correct
23 Correct 4 ms 12892 KB Output is correct
24 Correct 5 ms 12884 KB Output is correct
25 Correct 4 ms 12892 KB Output is correct
26 Correct 5 ms 12892 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 87168 KB Output is correct
2 Correct 281 ms 87144 KB Output is correct
3 Correct 255 ms 86920 KB Output is correct
4 Correct 272 ms 87504 KB Output is correct
5 Correct 104 ms 83152 KB Output is correct
6 Correct 104 ms 82748 KB Output is correct
7 Correct 94 ms 82868 KB Output is correct
8 Correct 104 ms 82840 KB Output is correct
9 Correct 189 ms 105852 KB Output is correct
10 Correct 131 ms 89456 KB Output is correct
11 Correct 106 ms 84672 KB Output is correct
12 Correct 88 ms 82632 KB Output is correct
13 Correct 126 ms 83284 KB Output is correct
14 Correct 154 ms 86988 KB Output is correct
15 Correct 228 ms 87348 KB Output is correct
16 Correct 263 ms 88120 KB Output is correct
17 Correct 104 ms 83868 KB Output is correct
18 Correct 106 ms 82808 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 89128 KB Output is correct
2 Correct 259 ms 89116 KB Output is correct
3 Correct 735 ms 112304 KB Output is correct
4 Correct 277 ms 88816 KB Output is correct
5 Correct 301 ms 110024 KB Output is correct
6 Correct 278 ms 106200 KB Output is correct
7 Correct 129 ms 84036 KB Output is correct
8 Correct 229 ms 100300 KB Output is correct
9 Correct 166 ms 106336 KB Output is correct
10 Correct 295 ms 122288 KB Output is correct
11 Correct 330 ms 126668 KB Output is correct
12 Correct 320 ms 132052 KB Output is correct
13 Correct 594 ms 126568 KB Output is correct
14 Correct 861 ms 122060 KB Output is correct
15 Correct 365 ms 122180 KB Output is correct
16 Correct 388 ms 124208 KB Output is correct
17 Correct 233 ms 108940 KB Output is correct
18 Correct 256 ms 119460 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2306 ms 403228 KB Output is correct
2 Correct 2315 ms 404552 KB Output is correct
3 Correct 3664 ms 459340 KB Output is correct
4 Correct 2086 ms 405432 KB Output is correct
5 Correct 1384 ms 438580 KB Output is correct
6 Correct 1075 ms 432036 KB Output is correct
7 Correct 609 ms 377800 KB Output is correct
8 Correct 1101 ms 421108 KB Output is correct
9 Correct 1100 ms 484144 KB Output is correct
10 Correct 1059 ms 465552 KB Output is correct
11 Correct 1073 ms 469472 KB Output is correct
12 Correct 1149 ms 477816 KB Output is correct
13 Correct 2228 ms 481364 KB Output is correct
14 Correct 3921 ms 468372 KB Output is correct
15 Correct 2075 ms 474064 KB Output is correct
16 Correct 2033 ms 472132 KB Output is correct
17 Correct 1022 ms 457468 KB Output is correct
18 Correct 1018 ms 449756 KB Output is correct