oj.uz

답안 #956770

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
956770 2024-04-02T12:55:58 Z tosivanmak 팀들 (IOI15_teams) C++17
77 / 100
 3676 ms 524288 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]];
    }
}reference,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);
   reference.init(n); reference.build(1,n,1);
   for(int i=1;i<=n;i++){
       for(auto& u: adj[i]){
        //    cout<<u<<" ";
           reference.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=reference.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=reference.qry(members[k[i]],l,l,1,n,1);
        ll val=reference.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:169:36: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  169 |             curver=st.seg[1].size()-1;
      |                    ~~~~~~~~~~~~~~~~^~
teams.cpp:175:36: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  175 |             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;
      |                    ~~~~~~~~~~~~~~~~^~

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 12912 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 3 ms 12888 KB Output is correct
5 Correct 4 ms 12892 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 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 5 ms 12912 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 6 ms 13660 KB Output is correct
13 Correct 5 ms 13404 KB Output is correct
14 Correct 4 ms 13148 KB Output is correct
15 Correct 3 ms 12900 KB Output is correct
16 Correct 4 ms 12920 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 4 ms 12892 KB Output is correct
19 Correct 3 ms 12888 KB Output is correct
20 Correct 4 ms 12888 KB Output is correct
21 Correct 3 ms 12892 KB Output is correct
22 Correct 3 ms 12880 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 12892 KB Output is correct
26 Correct 3 ms 12892 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 631 ms 158876 KB Output is correct
2 Correct 598 ms 159052 KB Output is correct
3 Correct 587 ms 158784 KB Output is correct
4 Correct 603 ms 159612 KB Output is correct
5 Correct 197 ms 152868 KB Output is correct
6 Correct 193 ms 153044 KB Output is correct
7 Correct 179 ms 152488 KB Output is correct
8 Correct 182 ms 152476 KB Output is correct
9 Correct 670 ms 191560 KB Output is correct
10 Correct 350 ms 160968 KB Output is correct
11 Correct 214 ms 154900 KB Output is correct
12 Correct 200 ms 151196 KB Output is correct
13 Correct 231 ms 152772 KB Output is correct
14 Correct 318 ms 159672 KB Output is correct
15 Correct 502 ms 159388 KB Output is correct
16 Correct 498 ms 158992 KB Output is correct
17 Correct 197 ms 152944 KB Output is correct
18 Correct 198 ms 150760 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 641 ms 160480 KB Output is correct
2 Correct 594 ms 160412 KB Output is correct
3 Correct 2826 ms 199152 KB Output is correct
4 Correct 662 ms 159656 KB Output is correct
5 Correct 1115 ms 174896 KB Output is correct
6 Correct 1097 ms 172004 KB Output is correct
7 Correct 201 ms 153004 KB Output is correct
8 Correct 876 ms 166956 KB Output is correct
9 Correct 735 ms 191348 KB Output is correct
10 Correct 1031 ms 197000 KB Output is correct
11 Correct 1113 ms 211332 KB Output is correct
12 Correct 1285 ms 213480 KB Output is correct
13 Correct 2649 ms 219176 KB Output is correct
14 Correct 3676 ms 216636 KB Output is correct
15 Correct 1337 ms 201560 KB Output is correct
16 Correct 1341 ms 203068 KB Output is correct
17 Correct 935 ms 179372 KB Output is correct
18 Correct 958 ms 192996 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1095 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -