oj.uz

답안 #956813

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
956813 2024-04-02T13:49:07 Z tosivanmak 팀들 (IOI15_teams) C++17
100 / 100
 3907 ms 484488 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,sse4")
#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(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]],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]],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:18: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   14 |     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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 12892 KB Output is correct
2 Correct 4 ms 12880 KB Output is correct
3 Correct 5 ms 12892 KB Output is correct
4 Correct 5 ms 13000 KB Output is correct
5 Correct 4 ms 12936 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 5 ms 13148 KB Output is correct
8 Correct 5 ms 12892 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 4 ms 12892 KB Output is correct
11 Correct 4 ms 12892 KB Output is correct
12 Correct 6 ms 13400 KB Output is correct
13 Correct 5 ms 13148 KB Output is correct
14 Correct 5 ms 12892 KB Output is correct
15 Correct 4 ms 12872 KB Output is correct
16 Correct 5 ms 12892 KB Output is correct
17 Correct 4 ms 12892 KB Output is correct
18 Correct 4 ms 12892 KB Output is correct
19 Correct 4 ms 12892 KB Output is correct
20 Correct 4 ms 12892 KB Output is correct
21 Correct 4 ms 12892 KB Output is correct
22 Correct 4 ms 12892 KB Output is correct
23 Correct 5 ms 12888 KB Output is correct
24 Correct 4 ms 12892 KB Output is correct
25 Correct 4 ms 12892 KB Output is correct
26 Correct 4 ms 12892 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 275 ms 87988 KB Output is correct
2 Correct 252 ms 88048 KB Output is correct
3 Correct 259 ms 87968 KB Output is correct
4 Correct 269 ms 88612 KB Output is correct
5 Correct 98 ms 83544 KB Output is correct
6 Correct 97 ms 83260 KB Output is correct
7 Correct 107 ms 83704 KB Output is correct
8 Correct 95 ms 83516 KB Output is correct
9 Correct 186 ms 106084 KB Output is correct
10 Correct 129 ms 89968 KB Output is correct
11 Correct 94 ms 85072 KB Output is correct
12 Correct 90 ms 83404 KB Output is correct
13 Correct 107 ms 84060 KB Output is correct
14 Correct 153 ms 87752 KB Output is correct
15 Correct 208 ms 88248 KB Output is correct
16 Correct 219 ms 87864 KB Output is correct
17 Correct 96 ms 83884 KB Output is correct
18 Correct 97 ms 82832 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 318 ms 88872 KB Output is correct
2 Correct 260 ms 89300 KB Output is correct
3 Correct 697 ms 112152 KB Output is correct
4 Correct 308 ms 89032 KB Output is correct
5 Correct 290 ms 110008 KB Output is correct
6 Correct 280 ms 106556 KB Output is correct
7 Correct 103 ms 84156 KB Output is correct
8 Correct 232 ms 100432 KB Output is correct
9 Correct 179 ms 106084 KB Output is correct
10 Correct 306 ms 122520 KB Output is correct
11 Correct 342 ms 126612 KB Output is correct
12 Correct 354 ms 131960 KB Output is correct
13 Correct 525 ms 126704 KB Output is correct
14 Correct 902 ms 122312 KB Output is correct
15 Correct 386 ms 122616 KB Output is correct
16 Correct 372 ms 123976 KB Output is correct
17 Correct 244 ms 109080 KB Output is correct
18 Correct 280 ms 119708 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2115 ms 402708 KB Output is correct
2 Correct 2028 ms 402224 KB Output is correct
3 Correct 3659 ms 455856 KB Output is correct
4 Correct 2054 ms 401852 KB Output is correct
5 Correct 1112 ms 436540 KB Output is correct
6 Correct 1042 ms 430388 KB Output is correct
7 Correct 632 ms 375372 KB Output is correct
8 Correct 934 ms 419252 KB Output is correct
9 Correct 1219 ms 484488 KB Output is correct
10 Correct 1122 ms 465668 KB Output is correct
11 Correct 1115 ms 468992 KB Output is correct
12 Correct 1266 ms 477040 KB Output is correct
13 Correct 2311 ms 483772 KB Output is correct
14 Correct 3907 ms 478296 KB Output is correct
15 Correct 1966 ms 482896 KB Output is correct
16 Correct 1994 ms 477256 KB Output is correct
17 Correct 1042 ms 462320 KB Output is correct
18 Correct 1065 ms 449948 KB Output is correct