Submission #956825

#	Time	Username	Problem	Language	Result	Execution time	Memory
956825		tosivanmak	Teams (IOI15_teams)	C++17	100 / 100	3921 ms	484144 KiB

teams

// #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 (stderr)

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 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23