oj.uz

Submission #799213

# Submission time Handle Problem Language Result Execution time Memory
799213 2023-07-31T10:48:43 Z Theo830 Teams (IOI15_teams) C++17
100 / 100
 1609 ms 135924 KB 
    #include <bits/stdc++.h>
    using namespace std;
    typedef int ll;
    const ll INF = 1e9+7;
    const ll MOD = 998244353;
    typedef pair<ll,ll> ii;
    #define iii pair<ll,ii>
    #define ull unsigned ll
    #define f(i,a,b) for(ll i = a;i < b;i++)
    #define pb push_back
    #define vll vector<ll>
    #define F first
    #define S second
    #define all(x) (x).begin(), (x).end()
    ///I hope I will get uprating and don't make mistakes
    ///I will never stop programming
    ///sqrt(-1) Love C++
    ///Please don't hack me
    ///@TheofanisOrfanou Theo830
    ///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
    ///Stay Calm
    ///Look for special cases
    ///Beware of overflow and array bounds
    ///Think the problem backwards
    ///Training
    //#include "teams.h"
    const ll sizz = 500005;
    vector<ii>arr;
    ll R[sizz];
    ll posa[sizz] = {0};
    ll vale[1005][25];
    ll n;
    vll el;
    ll C = 0;
    ll J = 0;
    vector<ll>seg[4 * sizz];
    void build(ll s,ll e,ll idx){
        if(s == e){
            seg[idx].pb(arr[s-1].S);
            return;
        }
        ll mid = (s + e) / 2;
        build(s,mid,idx * 2);
        build(mid+1,e,idx * 2 + 1);
        ll p1 = 0,p2 = 0;
        while(p1 < seg[idx * 2].size() || p2 < seg[idx * 2 + 1].size()){
            if(p1 == seg[idx * 2].size()){
                seg[idx].pb(seg[idx * 2 + 1][p2]);
                p2++;
            }
            else if(p2 == seg[idx * 2 + 1].size()){
                seg[idx].pb(seg[idx * 2][p1]);
                p1++;
            }
            else{
                if(seg[idx * 2][p1] < seg[idx * 2 + 1][p2]){
                    seg[idx].pb(seg[idx * 2][p1]);
                    p1++;
                }
                else{
                    seg[idx].pb(seg[idx * 2 + 1][p2]);
                    p2++;
                }
            }
        }
    }
    void solve(ll l,ll r,ll L,ll R,ll idx){
        if(l > r || L > R){
            return;
        }
        ll mid = (l + r) / 2;
        ll pos = lower_bound(all(el),seg[idx][mid]) - el.begin();
        if(pos != 0){
            pos--;
            vale[pos][C] = min(vale[pos][C],mid);
            solve(l,mid - 1,L,pos,idx);
            solve(mid+1,r,pos+1,R,idx);
        }
        else{
            solve(mid+1,r,pos,R,idx);
        }
    }
    void query(ll s,ll e,ll qs,ll qe,ll idx){
        if(qs <= s && e <= qe){
            vale[el.size()][C] = seg[idx].size();
            solve(0,seg[idx].size() - 1,J,el.size() - 1,idx);
            C++;
            return;
        }
        if(s > qe || qs > e){
            return;
        }
        ll mid = (s + e) / 2;
        query(s,mid,qs,qe,idx * 2);
        query(mid+1,e,qs,qe,idx * 2 + 1);
    }
    void init(int N, int A[], int B[]){
        n = N;
        f(i,0,n){
            arr.pb(ii(A[i],B[i]));
        }
        sort(all(arr));
        ll pos = 1;
        for(auto x:arr){
            R[x.F] = pos;
            pos++;
        }
        f(i,1,n+1){
            R[i] = max(R[i],R[i-1]);
        }
        f(i,0,1005){
            f(j,0,25){
                vale[i][j] = n;
            }
        }
        build(1,n,1);
    }
    int can(int M, int K[]) {
    	ll sum = 0;
    	vector<ii>ex;
    	sort(K,K+M);
    	f(i,0,M){
            sum += K[i];
            if(i > 0 && K[i] == K[i-1]){
                ex.back().S++;
            }
            else{
                ex.pb(ii(K[i],1));
            }
    	}
    	if(sum > n){
            return 0;
    	}
    	ll siz = ex.size();
    	f(i,0,siz){
            posa[i] = 0;
    	}
    	ll l = 1;
    	J = 0;
    	el.clear();
    	for(auto x:ex){
            el.pb(x.F - 1);
    	}
    	el.pb(INF);
    	for(auto x:ex){
            ll r = R[x.F];
            C = 0;
            query(1,n,l,r,1);
            ll em = x.S * x.F;
            for(ll i = siz + 1;i >= J;i--){
                f(u,0,C){
                    vale[i][u] = min(vale[i][u],vale[i+1][u]);
                    posa[i] += vale[i+1][u] - vale[i][u];
                    vale[i+1][u] = n;
                }
            }
            f(i,J,siz){
                ll E = min(posa[i],em);
                em -= E;
                posa[i] -= E;
                if(em == 0){
                    break;
                }
            }
            if(em > 0){
                f(i,0,siz + 5){
                    f(j,0,25){
                        vale[i][j] = n;
                    }
                }
                return 0;
            }
            l = r + 1;
            J++;
    	}
    	f(i,0,siz + 5){
            f(j,0,25){
                vale[i][j] = n;
            }
        }
    	return 1;
    }
    /*
    int main() {
        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];
        	}
        	printf("%d\n", can(M, K));
        }
        return 0;
    }
    */
    /*
    4
    2 4
    1 2
    2 3
    2 3
    2
    2 1 3
    2 1 1
    */

Compilation message

teams.cpp: In function 'void build(ll, ll, ll)':
teams.cpp:46:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         while(p1 < seg[idx * 2].size() || p2 < seg[idx * 2 + 1].size()){
      |               ~~~^~~~~~~~~~~~~~~~~~~~~
teams.cpp:46:46: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         while(p1 < seg[idx * 2].size() || p2 < seg[idx * 2 + 1].size()){
      |                                           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:47:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             if(p1 == seg[idx * 2].size()){
      |                ~~~^~~~~~~~~~~~~~~~~~~~~~
teams.cpp:51:24: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             else if(p2 == seg[idx * 2 + 1].size()){
      |                     ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'void solve(ll, ll, ll, ll, ll)':
teams.cpp:67:34: warning: declaration of 'R' shadows a global declaration [-Wshadow]
   67 |     void solve(ll l,ll r,ll L,ll R,ll idx){
      |                               ~~~^
teams.cpp:29:8: note: shadowed declaration is here
   29 |     ll R[sizz];
      |        ^
teams.cpp:72:53: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'll' {aka 'int'} may change value [-Wconversion]
   72 |         ll pos = lower_bound(all(el),seg[idx][mid]) - el.begin();
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
teams.cpp: In function 'void query(ll, ll, ll, ll, ll)':
teams.cpp:85:47: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'll' {aka 'int'} may change value [-Wconversion]
   85 |             vale[el.size()][C] = seg[idx].size();
      |                                  ~~~~~~~~~~~~~^~
teams.cpp:86:37: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'll' {aka 'int'} may change value [-Wconversion]
   86 |             solve(0,seg[idx].size() - 1,J,el.size() - 1,idx);
      |                     ~~~~~~~~~~~~~~~~^~~
teams.cpp:86:53: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'll' {aka 'int'} may change value [-Wconversion]
   86 |             solve(0,seg[idx].size() - 1,J,el.size() - 1,idx);
      |                                           ~~~~~~~~~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:134:22: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'll' {aka 'int'} may change value [-Wconversion]
  134 |      ll siz = ex.size();
      |               ~~~~~~~^~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47312 KB Output is correct
2 Correct 24 ms 47280 KB Output is correct
3 Correct 23 ms 47320 KB Output is correct
4 Correct 24 ms 47356 KB Output is correct
5 Correct 23 ms 47344 KB Output is correct
6 Correct 24 ms 47412 KB Output is correct
7 Correct 24 ms 47284 KB Output is correct
8 Correct 24 ms 47264 KB Output is correct
9 Correct 24 ms 47276 KB Output is correct
10 Correct 24 ms 47416 KB Output is correct
11 Correct 24 ms 47316 KB Output is correct
12 Correct 25 ms 47408 KB Output is correct
13 Correct 24 ms 47308 KB Output is correct
14 Correct 24 ms 47316 KB Output is correct
15 Correct 24 ms 47316 KB Output is correct
16 Correct 24 ms 47488 KB Output is correct
17 Correct 23 ms 47316 KB Output is correct
18 Correct 23 ms 47284 KB Output is correct
19 Correct 23 ms 47272 KB Output is correct
20 Correct 23 ms 47308 KB Output is correct
21 Correct 24 ms 47316 KB Output is correct
22 Correct 23 ms 47332 KB Output is correct
23 Correct 23 ms 47308 KB Output is correct
24 Correct 23 ms 47316 KB Output is correct
25 Correct 23 ms 47276 KB Output is correct
26 Correct 23 ms 47324 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 63968 KB Output is correct
2 Correct 71 ms 63912 KB Output is correct
3 Correct 70 ms 63936 KB Output is correct
4 Correct 72 ms 64432 KB Output is correct
5 Correct 60 ms 63572 KB Output is correct
6 Correct 61 ms 63480 KB Output is correct
7 Correct 61 ms 63524 KB Output is correct
8 Correct 60 ms 63564 KB Output is correct
9 Correct 56 ms 63580 KB Output is correct
10 Correct 56 ms 63272 KB Output is correct
11 Correct 56 ms 63332 KB Output is correct
12 Correct 55 ms 63424 KB Output is correct
13 Correct 61 ms 63752 KB Output is correct
14 Correct 65 ms 63732 KB Output is correct
15 Correct 78 ms 63912 KB Output is correct
16 Correct 68 ms 63808 KB Output is correct
17 Correct 60 ms 63780 KB Output is correct
18 Correct 65 ms 63884 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 64308 KB Output is correct
2 Correct 89 ms 64276 KB Output is correct
3 Correct 252 ms 67516 KB Output is correct
4 Correct 72 ms 64412 KB Output is correct
5 Correct 393 ms 64004 KB Output is correct
6 Correct 350 ms 63944 KB Output is correct
7 Correct 68 ms 63908 KB Output is correct
8 Correct 284 ms 63936 KB Output is correct
9 Correct 56 ms 63576 KB Output is correct
10 Correct 58 ms 63532 KB Output is correct
11 Correct 63 ms 63552 KB Output is correct
12 Correct 166 ms 63756 KB Output is correct
13 Correct 402 ms 64240 KB Output is correct
14 Correct 339 ms 65988 KB Output is correct
15 Correct 126 ms 64244 KB Output is correct
16 Correct 130 ms 64184 KB Output is correct
17 Correct 133 ms 64192 KB Output is correct
18 Correct 116 ms 64160 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 130360 KB Output is correct
2 Correct 310 ms 130328 KB Output is correct
3 Correct 930 ms 135924 KB Output is correct
4 Correct 297 ms 129940 KB Output is correct
5 Correct 1609 ms 127688 KB Output is correct
6 Correct 1478 ms 127768 KB Output is correct
7 Correct 260 ms 127680 KB Output is correct
8 Correct 1220 ms 127736 KB Output is correct
9 Correct 212 ms 127684 KB Output is correct
10 Correct 217 ms 125988 KB Output is correct
11 Correct 299 ms 126612 KB Output is correct
12 Correct 615 ms 127380 KB Output is correct
13 Correct 1566 ms 129156 KB Output is correct
14 Correct 1280 ms 132708 KB Output is correct
15 Correct 426 ms 130200 KB Output is correct
16 Correct 436 ms 130224 KB Output is correct
17 Correct 411 ms 129696 KB Output is correct
18 Correct 376 ms 129548 KB Output is correct