Submission #799213

#	Time	Username	Problem	Language	Result	Execution time	Memory
799213		Theo830	Teams (IOI15_teams)	C++17	100 / 100	1609 ms	135924 KiB

teams

    #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 (stderr)

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 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23