oj.uz

답안 #956776

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
956776 2024-04-02T13:00:24 Z tosivanmak 팀들 (IOI15_teams) C++17
77 / 100
 4000 ms 448792 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]];
    }
}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;
        while(l<=r){
            if(l==r)break;
            else if(l==r-1){if(ck(curver,k[i],l)){r=l;}else{l=r;}}
            else{
                ll mid=(l+r)>>1;
                if(ck(curver,k[i],mid)){r=mid;}
                else{l=mid;}
            }
        }
        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;
}

// int main() {
// 	// _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: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:168:36: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  168 |             curver=st.seg[1].size()-1;
      |                    ~~~~~~~~~~~~~~~~^~
teams.cpp:174:36: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  174 |             curver=st.seg[1].size()-1;
      |                    ~~~~~~~~~~~~~~~~^~
teams.cpp:178:36: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  178 |             curver=st.seg[1].size()-1;
      |                    ~~~~~~~~~~~~~~~~^~

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12888 KB Output is correct
3 Correct 4 ms 12888 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 12888 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 4 ms 13148 KB Output is correct
8 Correct 4 ms 12888 KB Output is correct
9 Correct 4 ms 12888 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 7 ms 13660 KB Output is correct
13 Correct 5 ms 13148 KB Output is correct
14 Correct 4 ms 12992 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 12908 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 13012 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 12980 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

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 87232 KB Output is correct
2 Correct 260 ms 87072 KB Output is correct
3 Correct 263 ms 86892 KB Output is correct
4 Correct 268 ms 87372 KB Output is correct
5 Correct 101 ms 83000 KB Output is correct
6 Correct 99 ms 83624 KB Output is correct
7 Correct 97 ms 83564 KB Output is correct
8 Correct 96 ms 83784 KB Output is correct
9 Correct 525 ms 123624 KB Output is correct
10 Correct 240 ms 90340 KB Output is correct
11 Correct 107 ms 85192 KB Output is correct
12 Correct 93 ms 83048 KB Output is correct
13 Correct 114 ms 84060 KB Output is correct
14 Correct 155 ms 87756 KB Output is correct
15 Correct 241 ms 88024 KB Output is correct
16 Correct 252 ms 88208 KB Output is correct
17 Correct 98 ms 83864 KB Output is correct
18 Correct 101 ms 82840 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 269 ms 87880 KB Output is correct
2 Correct 266 ms 88360 KB Output is correct
3 Correct 1791 ms 127412 KB Output is correct
4 Correct 261 ms 88520 KB Output is correct
5 Correct 897 ms 105652 KB Output is correct
6 Correct 803 ms 103072 KB Output is correct
7 Correct 104 ms 84016 KB Output is correct
8 Correct 706 ms 97876 KB Output is correct
9 Correct 562 ms 123580 KB Output is correct
10 Correct 902 ms 124440 KB Output is correct
11 Correct 966 ms 140140 KB Output is correct
12 Correct 1121 ms 146916 KB Output is correct
13 Correct 1760 ms 150324 KB Output is correct
14 Correct 2423 ms 147216 KB Output is correct
15 Correct 991 ms 130216 KB Output is correct
16 Correct 940 ms 131180 KB Output is correct
17 Correct 749 ms 110092 KB Output is correct
18 Correct 760 ms 123540 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2196 ms 406044 KB Output is correct
2 Correct 2210 ms 406332 KB Output is correct
3 Execution timed out 4040 ms 448792 KB Time limit exceeded
4 Halted 0 ms 0 KB -