Submission #542114

#	Time	Username	Problem	Language	Result	Execution time	Memory
542114		wildturtle	Teams (IOI15_teams)	C++17	0 / 100	4067 ms	94244 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
#define ll long long
#define f first
#define sc second
#define pb push_back
using namespace std;
int a,b,c,d,i,e,f,g,n,m,l;
int tree[4*500005],lef[3*500005],righ[4*500005];
int root[500005],k[500005],dp[500005];
int snode,prevroot,tim;
set <int> st1;
set < pair <int,int> > st;
vector <int> v[500005];
void build(int node,int le,int ri) {
    if(le==ri) {
        tree[node]=0;
        return;
    }
    snode++;
    lef[node]=snode;
    build(snode,le,(le+ri)/2);
    snode++;
    righ[node]=snode;
    build(snode,(le+ri)/2+1,ri);
    tree[node]=tree[lef[node]]+tree[righ[node]];
}
void update(int node,int prevnode,int le,int ri,int idx) {
    if(ri<idx || le>idx) return;
    if(le==ri) {
        tree[node]=tree[prevnode]+1;
        return;
    }
    if(idx<=(le+ri)/2) { 
        snode++; lef[node]=snode; righ[node]=righ[prevnode];
        update(snode,lef[prevnode],le,(le+ri)/2,idx); 
    } else {
        snode++; righ[node]=snode; lef[node]=lef[prevnode];
        update(snode,righ[prevnode],(le+ri)/2+1,ri,idx);
    }
    tree[node]=tree[lef[node]]+tree[righ[node]];
    
}
int getans(int node,int start,int end,int le,int ri) {
    if(ri<start || le>end) return 0;
    if(start<=le && ri<=end) return tree[node];
return getans(lef[node],le,(le+ri)/2,start,end)+getans(righ[node],(le+ri)/2+1,ri,start,end);
}
int Z(int x,int y) {
    return getans(root[y],y,n,1,n)-getans(root[x],y,n,1,n);
}
int go(int x,int y) {
    int le=k[b]+1; 
    int ri=n;
    int ans=0;
    while(le<=ri) {
        int mid=(le+ri)/2;
        if(dp[a]-dp[b]<-(getans(root[k[b]],mid,n,1,n)-getans(root[k[a]],mid,n,1,n))) {
            ans=mid; ri=mid-1;
        } else le=mid+1;
    }
    return ans;
}
void add(int x) {
	if(!st1.size()) { st1.insert(x); return; }
    int pat=*(--st1.end());
    st1.insert(x);
    tim=go(pat,x);
    if(tim) st.insert({tim,x});
}
void del(int x) {
    if(!st1.count(x)) return;
    st1.erase(x);
    if(!st1.size()) return;
    int pat=-1;
    int did=-1;
    if(*st1.begin()<x) pat=*(--st1.upper_bound(x));
    if(st1.upper_bound(x)!=st1.end()) did=*st1.upper_bound(x);
    if(did!=-1) {
        tim=go(x,did);
        if(tim) st.erase({tim,did});
    }
    if(pat!=-1) {
        tim=go(pat,x);
        if(tim) st.erase({tim,x});
    }
    if(did!=-1 && pat!=-1) {
        tim=go(pat,did);
        if(tim) st.insert({tim,did});
    }
}
int can(int M, int K[]) {
    st.clear();
    st1.clear();
    m=M;
    for(int i=m;i>=1;i--) {
        k[i]=K[i-1];
        dp[i]=0;
    }
    int sum=0;
	for(int i=1;i<=m;i++) {
	    sum+=k[i];
	}
	if(sum>n) return 0;
	sort(k+1,k+1+m);
	dp[0]=0;
	add(0);
	for(int i=1;i<=m;i++) dp[i]=1e9;
	for(int i=1;i<=m;i++) {
	    while(st.size()) {
	    	multiset < pair <int,int> > :: iterator it = st.begin();
	        if((*it).f<=k[i]) del((*it).sc);
	        else break;
	    }
	    int idx=*(--st1.end());
	    dp[i]=dp[idx]+Z(k[idx],k[i])-k[i];
	    if(dp[i]<0) return 0;
	    add(i);
	}
	return 1;
}
void init(int N, int A[], int B[]) {
    n=N;
    for(int i=0;i<N;i++) {
	    v[A[i]].pb(B[i]);
	}
	snode=1;
	root[0]=snode;
	build(1,1,n);
	for(int i=1;i<=N;i++) {
        prevroot=root[i-1];
        root[i]=root[i-1];
        for(int j=0;j<v[i].size();j++) {
            snode++;
            root[i]=snode;
            update(root[i],prevroot,1,n,v[i][j]);
            prevroot=root[i];
        }
	}
}

Compilation message (stderr)

teams.cpp: In function 'int go(int, int)':
teams.cpp:52:12: warning: unused parameter 'x' [-Wunused-parameter]
   52 | int go(int x,int y) {
      |        ~~~~^
teams.cpp:52:18: warning: unused parameter 'y' [-Wunused-parameter]
   52 | int go(int x,int y) {
      |              ~~~~^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:96:13: warning: declaration of 'i' shadows a global declaration [-Wshadow]
   96 |     for(int i=m;i>=1;i--) {
      |             ^
teams.cpp:8:13: note: shadowed declaration is here
    8 | int a,b,c,d,i,e,f,g,n,m,l;
      |             ^
teams.cpp:101:10: warning: declaration of 'i' shadows a global declaration [-Wshadow]
  101 |  for(int i=1;i<=m;i++) {
      |          ^
teams.cpp:8:13: note: shadowed declaration is here
    8 | int a,b,c,d,i,e,f,g,n,m,l;
      |             ^
teams.cpp:108:10: warning: declaration of 'i' shadows a global declaration [-Wshadow]
  108 |  for(int i=1;i<=m;i++) dp[i]=1e9;
      |          ^
teams.cpp:8:13: note: shadowed declaration is here
    8 | int a,b,c,d,i,e,f,g,n,m,l;
      |             ^
teams.cpp:109:10: warning: declaration of 'i' shadows a global declaration [-Wshadow]
  109 |  for(int i=1;i<=m;i++) {
      |          ^
teams.cpp:8:13: note: shadowed declaration is here
    8 | int a,b,c,d,i,e,f,g,n,m,l;
      |             ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:124:13: warning: declaration of 'i' shadows a global declaration [-Wshadow]
  124 |     for(int i=0;i<N;i++) {
      |             ^
teams.cpp:8:13: note: shadowed declaration is here
    8 | int a,b,c,d,i,e,f,g,n,m,l;
      |             ^
teams.cpp:130:10: warning: declaration of 'i' shadows a global declaration [-Wshadow]
  130 |  for(int i=1;i<=N;i++) {
      |          ^
teams.cpp:8:13: note: shadowed declaration is here
    8 | int a,b,c,d,i,e,f,g,n,m,l;
      |             ^
teams.cpp:133:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         for(int j=0;j<v[i].size();j++) {
      |                     ~^~~~~~~~~~~~

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