Submission #386789

#	Time	Username	Problem	Language	Result	Execution time	Memory
386789		mehrdad_sohrabi	Teams (IOI15_teams)	C++14	100 / 100	2054 ms	258632 KiB

teams

/// Black lives matter
#include <bits/stdc++.h>
#include "teams.h"
/// 500 485 462 A4
using namespace std;
typedef int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=5e5+100,M=50;
ll n;
ll roo[N*M];
ll se[N*M];
ll st=1;
ll LL[N*M],RR[N*M];
ll add(ll nod,ll l,ll r,ll id,ll val){
    ll NOD=st;
    st++;
    se[NOD]=se[nod];
    LL[NOD]=LL[nod];
    RR[NOD]=RR[nod];
    if (r-l==1){
        se[NOD]+=val;
        return NOD;
    }
    ll mid=(r+l)/2;
    if (mid>id) LL[NOD]=add(LL[NOD],l,mid,id,val);
    else RR[NOD]=add(RR[NOD],mid,r,id,val);
    se[NOD]=se[LL[NOD]]+se[RR[NOD]];
    return NOD;
}
ll fin(ll nod1,ll nod2,ll l,ll r,ll val){
    if (r-l==1){
        if (se[nod2]-se[nod1]<val) return n+1;
        return l;
    }
    ll mid=(r+l)/2;
    if (se[LL[nod2]]-se[LL[nod1]]>=val) return fin(LL[nod1],LL[nod2],l,mid,val);
    val-=se[LL[nod2]]-se[LL[nod1]];
    return fin(RR[nod1],RR[nod2],mid,r,val);
}
ll seg[N*M];
ll L[N*M],R[N*M];
ll ts=1;
ll root[N];
ll upd(ll nod,ll l,ll r,ll id,ll val){
    ll NOD=ts;
    ts++;
    seg[NOD]=seg[nod];
    L[NOD]=L[nod];
    R[NOD]=R[nod];
    if (r-l==1){
        seg[NOD]+=val;
        return NOD;
    }
    ll mid=(r+l)/2;
    if (mid>id) L[NOD]=upd(L[NOD],l,mid,id,val);
    else R[NOD]=upd(R[NOD],mid,r,id,val);
    seg[NOD]=seg[L[NOD]]+seg[R[NOD]];
    return NOD;
}
ll get(ll nod,ll l,ll r,ll le,ll re){
    if (l>=re || le>=r) return 0;
    if (l>=le && r<=re) return seg[nod];
    ll mid=(r+l)/2;
    return get(L[nod],l,mid,le,re)+get(R[nod],mid,r,le,re);
}
vector <int> a,b;
void init(int32_t N, int32_t A[], int32_t B[]) {
    n=N;
    vector <pii> aa,bb,cc;
    b.pb(0);
    for (int i=0;i<n;i++){
        aa.pb({A[i],B[i]});
        b.pb(B[i]);
    }
    sort(aa.begin(),aa.end());
    sort(b.begin(),b.end());
    a.pb(0);
    for (int i=0;i<aa.size();i++){
        a.pb(aa[i].F);
        bb.pb({aa[i].S,i+1});

    }
    sort(bb.begin(),bb.end());
    ll last=0;
    for (int i=1;i<=n;i++){
        ll x=bb[i-1].F,y=bb[i-1].S;
        root[i]=upd(root[i-1],1,n+1,y,1);
        cc.pb({y,i});
    }
    sort(cc.begin(),cc.end());
    for (int i=1;i<=n;i++){
        ll x=cc[i-1].F,y=cc[i-1].S;
        roo[i]=add(roo[i-1],1,n+1,y,1);
    }
}
ll getk(ll L,ll R,ll k){
    /// baste baz
    ll x=fin(roo[L-1],roo[R-1],1,n+1,k);
    ///
    return x;
    ll l=0,r=n+1;
    while(r-l>1){
        ll mid=(r+l)/2;
        if (get(root[mid],1,n+1,L,R)>=k) r=mid;
        else l=mid;
    }
    if (x!=r) cout <<1/0 <<  endl;
    return r;
}
int32_t can(int32_t M, int32_t K[]) {
    vector <pii> m;
    sort(K,K+M);
    for (int i=0;i<M;i++){
        ll s=0;
        ll j=i;
        while(j<M && K[j]==K[i]) j++,s+=K[i];
        m.pb({K[i],s});
        i=j-1;
    }
    vector <pair <int,int> > agh;
    agh.pb({0,n});
    for (int i=0;i<m.size();i++){
        ll x=lower_bound(b.begin(),b.end(),m[i].F)-b.begin()-1;
        if (x==n) return 0;
        while(agh.size() && agh.back().S<=x) agh.pop_back();
        ll z=upper_bound(a.begin(),a.end(),m[i].F)-a.begin();
        z--;
        if (z==0) return 0;
        while(agh.size()){
            ll t=agh.back().F;
            ll cnt=m[i].S+get(root[x],1,n+1,t+1,z+1);
            ll d=getk(t+1,z+1,cnt);
            if (d==n+1 && agh.size()==1) return 0;
          //  if (d==agh.back().S) cout << 1/0;
          //  cout << d << " ddddddd " << agh.back().S << endl;
            if (d<=agh.back().S){
                agh.pb({z,d});
                break;
            }
            else{
                if (agh.size()==1) return 0;
                m[i].S-=get(root[agh.back().S],1,n+1,t+1,z+1)-get(root[x],1,n+1,t+1,z+1);
                x=max(x,agh.back().S);
                agh.pop_back();
            }
        }
    }
    return 1;
}
/*
int32_t A[200],B[200],K[200];
int32_t main(){
    ll N,q;
	cin >> N;
	for(int i=0;i<N;i++){
		cin >> A[i] >> B[i];
	}
	init(N, A, B);
	cin >> q;
	for(ll i = 0; i < q; i++){
        ll m;
		cin >> m;
		for(ll j = 0; j < m; j++){
			cin >> K[j];
		}
		cout << can(m, K) << " ans" << endl;
	}
}
*/
/*
4
2 4
1 2
2 3
2 3
2
2 1 3
2 1 1
*/

Compilation message (stderr)

teams.cpp: In function 'void init(int32_t, int32_t*, int32_t*)':
teams.cpp:77:46: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   77 | void init(int32_t N, int32_t A[], int32_t B[]) {
      |                                              ^
teams.cpp:18:11: note: shadowed declaration is here
   18 | const int N=5e5+100,M=50;
      |           ^
teams.cpp:88:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i=0;i<aa.size();i++){
      |                  ~^~~~~~~~~~
teams.cpp:96:12: warning: unused variable 'x' [-Wunused-variable]
   96 |         ll x=bb[i-1].F,y=bb[i-1].S;
      |            ^
teams.cpp:102:12: warning: unused variable 'x' [-Wunused-variable]
  102 |         ll x=cc[i-1].F,y=cc[i-1].S;
      |            ^
teams.cpp:94:8: warning: unused variable 'last' [-Wunused-variable]
   94 |     ll last=0;
      |        ^~~~
teams.cpp: In function 'll getk(ll, ll, ll)':
teams.cpp:106:23: warning: declaration of 'R' shadows a global declaration [-Wshadow]
  106 | ll getk(ll L,ll R,ll k){
      |                       ^
teams.cpp:51:11: note: shadowed declaration is here
   51 | ll L[N*M],R[N*M];
      |           ^
teams.cpp:106:23: warning: declaration of 'L' shadows a global declaration [-Wshadow]
  106 | ll getk(ll L,ll R,ll k){
      |                       ^
teams.cpp:51:4: note: shadowed declaration is here
   51 | ll L[N*M],R[N*M];
      |    ^
teams.cpp:117:23: warning: division by zero [-Wdiv-by-zero]
  117 |     if (x!=r) cout <<1/0 <<  endl;
      |                      ~^~
teams.cpp: In function 'int32_t can(int32_t, int32_t*)':
teams.cpp:120:35: warning: declaration of 'M' shadows a global declaration [-Wshadow]
  120 | int32_t can(int32_t M, int32_t K[]) {
      |                                   ^
teams.cpp:18:21: note: shadowed declaration is here
   18 | const int N=5e5+100,M=50;
      |                     ^
teams.cpp:132:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for (int i=0;i<m.size();i++){
      |                  ~^~~~~~~~~
teams.cpp:133:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'll' {aka 'int'} may change value [-Wconversion]
  133 |         ll x=lower_bound(b.begin(),b.end(),m[i].F)-b.begin()-1;
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:136:51: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'll' {aka 'int'} may change value [-Wconversion]
  136 |         ll z=upper_bound(a.begin(),a.end(),m[i].F)-a.begin();
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23