Submission #306480

#	Time	Username	Problem	Language	Result	Execution time	Memory
306480		Pajaraja	Teams (IOI15_teams)	C++17	100 / 100	943 ms	170444 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define MAXN 500007
using namespace std;
int per[25*MAXN],lc[25*MAXN],rc[25*MAXN],t,n,st[MAXN],dp[MAXN],m,nxt[MAXN],prv[MAXN],top,fas[MAXN];
vector<int> l[MAXN],v,c,z[MAXN];
void makeper(int l,int r,int ind)
{
    if(l==r) return;
    int s=(l+r)/2;
    lc[ind]=++t;
    makeper(l,s,lc[ind]);
    rc[ind]=++t;
    makeper(s+1,r,rc[ind]);
}
void makenewper(int l,int r,int v,int ind,int inh)
{
    per[ind]=per[inh]+1;
    if(l==r) return;
    int s=(l+r)/2;
    if(s>=v)
    {
        rc[ind]=rc[inh];
        lc[ind]=++t;
        makenewper(l,s,v,lc[ind],lc[inh]);
    }
    else
    {
        lc[ind]=lc[inh];
        rc[ind]=++t;
        makenewper(s+1,r,v,rc[ind],rc[inh]);
    }
}
int query(int l,int r,int lt,int rt,int ind)
{
    if(l>=lt && r<=rt) return per[ind];
    if(r<lt || l>rt) return 0;
    int s=(l+r)/2;
    return query(l,s,lt,rt,lc[ind])+query(s+1,r,lt,rt,rc[ind]);
}
void init(int N, int A[], int B[])
{
    n=N;
    for(int i=0;i<n;i++) l[B[i]].push_back(A[i]);
    makeper(1,n,t);
    int last=0;
    for(int i=n;i>=0;i--)
    {
        for(int j=0;j<l[i].size();j++) {int newlast=++t; makenewper(1,n,l[i][j],newlast,last); last=newlast;}
        st[i]=last;
    }
}
int overtake(int a,int b)
{
    int l=b+1,r=m-1;
    if(dp[a]+query(1,n,v[a]+1,v[b],st[v[m-1]])>dp[b]) return m;
    while(l!=r)
    {
        int s=(l+r)/2;
        if(dp[a]+query(1,n,v[a]+1,v[b],st[v[s]])<=dp[b]) r=s;
        else l=s+1;
    }
    return l;
}
int can(int M, int K[])
{
    sort(K,K+M);
    v.clear(); c.clear();
    int sz=0; for(int i=0;i<M;i++) {sz+=K[i]; if(sz>n) return 0;}
	int cnt=0;
	v.push_back(0); c.push_back(0);
	for(int i=0;i<M;i++)
    {
        cnt++;
        if(i==M-1 || K[i]!=K[i+1]) {v.push_back(K[i]); c.push_back(cnt); cnt=0;}
    }
    m=v.size(); prv[0]=nxt[0]=-1; dp[0]=0; top=0;
    for(int i=0;i<=m;i++) z[i].clear();
    for(int i=1;i<m;i++)
    {
        for(int j=0;j<z[i].size();j++) if(!fas[z[i][j]])
        {
            int t=z[i][j];
            if(t==top) {fas[top]=true; top=prv[t]; nxt[top]=-1; continue;}
            nxt[prv[t]]=nxt[t];
            prv[nxt[t]]=prv[t];
            z[max(i,overtake(prv[t],nxt[t]))].push_back(nxt[t]);
            fas[t]=true;
        }
        dp[i]=query(1,n,v[top]+1,v[i],st[v[i]])+dp[top];
        fas[i]=false; nxt[i]=-1; prv[i]=top; nxt[top]=i;
        dp[i]-=c[i]*v[i];
        if(dp[i]<0) return 0;
        while(dp[i]<dp[top]) {fas[top]=true; top=prv[top]; nxt[top]=i; prv[i]=top;}
        top=i;
        if(i!=m-1) z[overtake(prv[top],top)].push_back(top);
    }
    return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void makeper(int, int, int)':
teams.cpp:7:33: warning: declaration of 'l' shadows a global declaration [-Wshadow]
    7 | void makeper(int l,int r,int ind)
      |                                 ^
teams.cpp:6:13: note: shadowed declaration is here
    6 | vector<int> l[MAXN],v,c,z[MAXN];
      |             ^
teams.cpp: In function 'void makenewper(int, int, int, int, int)':
teams.cpp:16:50: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   16 | void makenewper(int l,int r,int v,int ind,int inh)
      |                                                  ^
teams.cpp:6:21: note: shadowed declaration is here
    6 | vector<int> l[MAXN],v,c,z[MAXN];
      |                     ^
teams.cpp:16:50: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   16 | void makenewper(int l,int r,int v,int ind,int inh)
      |                                                  ^
teams.cpp:6:13: note: shadowed declaration is here
    6 | vector<int> l[MAXN],v,c,z[MAXN];
      |             ^
teams.cpp: In function 'int query(int, int, int, int, int)':
teams.cpp:34:44: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   34 | int query(int l,int r,int lt,int rt,int ind)
      |                                            ^
teams.cpp:6:13: note: shadowed declaration is here
    6 | vector<int> l[MAXN],v,c,z[MAXN];
      |             ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int j=0;j<l[i].size();j++) {int newlast=++t; makenewper(1,n,l[i][j],newlast,last); last=newlast;}
      |                     ~^~~~~~~~~~~~
teams.cpp: In function 'int overtake(int, int)':
teams.cpp:55:9: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   55 |     int l=b+1,r=m-1;
      |         ^
teams.cpp:6:13: note: shadowed declaration is here
    6 | vector<int> l[MAXN],v,c,z[MAXN];
      |             ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:77:13: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   77 |     m=v.size(); prv[0]=nxt[0]=-1; dp[0]=0; top=0;
      |       ~~~~~~^~
teams.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for(int j=0;j<z[i].size();j++) if(!fas[z[i][j]])
      |                     ~^~~~~~~~~~~~
teams.cpp:83:17: warning: declaration of 't' shadows a global declaration [-Wshadow]
   83 |             int t=z[i][j];
      |                 ^
teams.cpp:5:42: note: shadowed declaration is here
    5 | int per[25*MAXN],lc[25*MAXN],rc[25*MAXN],t,n,st[MAXN],dp[MAXN],m,nxt[MAXN],prv[MAXN],top,fas[MAXN];
      |                                          ^

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