oj.uz

답안 #956809

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
956809 2024-04-02T13:36:17 Z tosivanmak 팀들 (IOI15_teams) C++17
77 / 100
 4000 ms 496356 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(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);
        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:173:36: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  173 |             curver=st.seg[1].size()-1;
      |                    ~~~~~~~~~~~~~~~~^~
teams.cpp:179:36: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  179 |             curver=st.seg[1].size()-1;
      |                    ~~~~~~~~~~~~~~~~^~
teams.cpp:183:36: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  183 |             curver=st.seg[1].size()-1;
      |                    ~~~~~~~~~~~~~~~~^~

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 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 3 ms 12896 KB Output is correct
7 Correct 3 ms 13148 KB Output is correct
8 Correct 4 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 3 ms 12912 KB Output is correct
11 Correct 3 ms 12888 KB Output is correct
12 Correct 5 ms 13656 KB Output is correct
13 Correct 4 ms 13168 KB Output is correct
14 Correct 4 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 12888 KB Output is correct
18 Correct 3 ms 12888 KB Output is correct
19 Correct 3 ms 12888 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 3 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 4 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

# 결과 실행 시간 메모리 Grader output
1 Correct 270 ms 87904 KB Output is correct
2 Correct 248 ms 87984 KB Output is correct
3 Correct 241 ms 87972 KB Output is correct
4 Correct 266 ms 88608 KB Output is correct
5 Correct 96 ms 83512 KB Output is correct
6 Correct 98 ms 83360 KB Output is correct
7 Correct 92 ms 83260 KB Output is correct
8 Correct 95 ms 83560 KB Output is correct
9 Correct 245 ms 123488 KB Output is correct
10 Correct 131 ms 90016 KB Output is correct
11 Correct 100 ms 85260 KB Output is correct
12 Correct 92 ms 83388 KB Output is correct
13 Correct 110 ms 84060 KB Output is correct
14 Correct 164 ms 87724 KB Output is correct
15 Correct 241 ms 88456 KB Output is correct
16 Correct 269 ms 87940 KB Output is correct
17 Correct 96 ms 83860 KB Output is correct
18 Correct 98 ms 83120 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 271 ms 89232 KB Output is correct
2 Correct 279 ms 89720 KB Output is correct
3 Correct 878 ms 128796 KB Output is correct
4 Correct 273 ms 88592 KB Output is correct
5 Correct 299 ms 106316 KB Output is correct
6 Correct 272 ms 103104 KB Output is correct
7 Correct 101 ms 84280 KB Output is correct
8 Correct 239 ms 97924 KB Output is correct
9 Correct 246 ms 123376 KB Output is correct
10 Correct 334 ms 124532 KB Output is correct
11 Correct 352 ms 141756 KB Output is correct
12 Correct 416 ms 147064 KB Output is correct
13 Correct 667 ms 150484 KB Output is correct
14 Correct 1084 ms 147560 KB Output is correct
15 Correct 410 ms 130360 KB Output is correct
16 Correct 422 ms 131796 KB Output is correct
17 Correct 257 ms 110308 KB Output is correct
18 Correct 275 ms 123584 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2305 ms 400128 KB Output is correct
2 Correct 2160 ms 402268 KB Output is correct
3 Execution timed out 4103 ms 496356 KB Time limit exceeded
4 Halted 0 ms 0 KB -