Submission #386750

#	Time	Username	Problem	Language	Result	Execution time	Memory
386750		mehrdad_sohrabi	Teams (IOI15_teams)	C++14	13 / 100	3151 ms	273208 KiB

teams

/// Black lives matter
#include <bits/stdc++.h>
#include "teams.h"
/// 500 485 462 A4
using namespace std;
typedef long long 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=2e5+100,M=50;
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;
ll n;
void init(int32_t N, int32_t A[], int32_t B[]) {
    n=N;
    vector <pii> aa,bb;
    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);
  //      cout << i << " " << y  << " ijed " << endl;
    }
}
ll getk(ll L,ll R,ll k){
    /// baste baz
    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;
    }
    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;
        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;
    //    cout << x << " x " << z << endl;
        while(agh.size()){
            ll t=agh.back().F;
            ll cnt=m[i].S+get(root[x],1,n+1,t+1,z+1);
      //      cout << t << " " << cnt << " cnt " << endl;
            ll d=getk(t+1,z+1,cnt);
            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:47:46: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   47 | void init(int32_t N, int32_t A[], int32_t B[]) {
      |                                              ^
teams.cpp:18:11: note: shadowed declaration is here
   18 | const int N=2e5+100,M=50;
      |           ^
teams.cpp:58:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i=0;i<aa.size();i++){
      |                  ~^~~~~~~~~~
teams.cpp:66:12: warning: unused variable 'x' [-Wunused-variable]
   66 |         ll x=bb[i-1].F,y=bb[i-1].S;
      |            ^
teams.cpp:64:8: warning: unused variable 'last' [-Wunused-variable]
   64 |     ll last=0;
      |        ^~~~
teams.cpp: In function 'll getk(ll, ll, ll)':
teams.cpp:71:23: warning: declaration of 'R' shadows a global declaration [-Wshadow]
   71 | ll getk(ll L,ll R,ll k){
      |                       ^
teams.cpp:20:11: note: shadowed declaration is here
   20 | ll L[N*M],R[N*M];
      |           ^
teams.cpp:71:23: warning: declaration of 'L' shadows a global declaration [-Wshadow]
   71 | ll getk(ll L,ll R,ll k){
      |                       ^
teams.cpp:20:4: note: shadowed declaration is here
   20 | ll L[N*M],R[N*M];
      |    ^
teams.cpp: In function 'int32_t can(int32_t, int32_t*)':
teams.cpp:81:35: warning: declaration of 'M' shadows a global declaration [-Wshadow]
   81 | int32_t can(int32_t M, int32_t K[]) {
      |                                   ^
teams.cpp:18:21: note: shadowed declaration is here
   18 | const int N=2e5+100,M=50;
      |                     ^
teams.cpp:93:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i=0;i<m.size();i++){
      |                  ~^~~~~~~~~

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