Submission #799590

#	Time	Username	Problem	Language	Result	Execution time	Memory
799590		I_Love_EliskaM_	Teams (IOI15_teams)	C++14	100 / 100	687 ms	156472 KiB

teams

#include "teams.h"
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(),x.end()
using ll = long long;
#define pi pair<int,int>
#define f first
#define s second

const int K=2e7;
int L[K],R[K],s[K];
 
const int sz=1<<19;
int nxt=1;
int add(int v, int l, int r, int i, int x) {
  if (r-l==1) {
    s[nxt]=s[v]+x;
    return nxt++;
  }
  int m=(l+r)>>1;
  if (i<m) {
    if (L[v]==0) L[v]=nxt++;
    int n = add(L[v],l,m,i,x);
    L[nxt]=n, R[nxt]=R[v], s[nxt]=s[v]+x;
    return nxt++;
  } else {
    if (R[v]==0) R[v]=nxt++;
    int n = add(R[v],m,r,i,x);
    L[nxt]=L[v], R[nxt]=n, s[nxt]=s[v]+x;
    return nxt++;
  }
}
int add(int v, int i, int x) {
  return add(v,0,sz,i,x);
}
 
int sum(int v, int l, int r, int lx, int rx) {
  if (lx<=l && r<=rx) return s[v];
  int m=(l+r)>>1;
  int lq = L[v] ? ( (lx>=m)?0:sum(L[v],l,m,lx,rx) ) : 0;
  int rq = R[v] ? ( (rx<=m)?0:sum(R[v],m,r,lx,rx) ) : 0;
  return lq+rq;
}
int sum(int v, int l, int r) {
  if (l>=r) return 0;
  return sum(v,0,sz,l,r);
}
int st[(int)5e5+55];

pi a[(int)5e5];
int n;

void init(int _n, int f[], int s[]) {
  n=_n;
  forn(i,n) a[i]={f[i],s[i]};
  vector<vector<int>> v(n+1);
  forn(i,n) v[a[i].s].pb(i);
  st[n+1]=0;
  for(int i=n;i>0;--i) {
    st[i]=st[i+1];
    for(auto&x:v[i]) {
      auto t=add(st[i],a[x].f,1);
      st[i]=t;
    }
  } 
}

int can(int m, int k[]) {
  vector<int> v(m);
  forn(i,m) v[i]=k[i];
  sort(all(v));
  int s=0; forn(i,m) s+=k[i];
  if (s>n) return 0;

  vector<pi> z;
  forn(i,m) {
    if (!z.size()) {
      z.pb({v[i],1}); continue;
    }
    if (v[i]==z.back().f) z.back().s++;
    else z.pb({v[i],1});
  }
  int t=z.size();

  vector<int> dp(t+1,-1e9);
  dp[0]=0;

  forn(i,t) {
    int mx=i;
    for(int j=i-1; j>=0; --j) {
      if (dp[j]<=dp[mx]) continue;
      int cnt;
      if (mx==0) {
        cnt=sum(st[z[i].f],0,z[i].f+1);
      } else {
        cnt=sum(st[z[i].f],z[mx-1].f+1,z[i].f+1);
      }
      dp[i+1]=max(dp[i+1],dp[mx]-cnt);
      mx=j;
    }
    int cnt;
    if (mx==0) {
      cnt=sum(st[z[i].f],0,z[i].f+1);
    } else {
      cnt=sum(st[z[i].f],z[mx-1].f+1,z[i].f+1);
    }
    dp[i+1]=max(dp[i+1],dp[mx]-cnt);
    dp[i+1]+=z[i].f*z[i].s;
    if (dp[i+1]>0) return 0;
  }
  return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:12:11: warning: declaration of 'second' shadows a global declaration [-Wshadow]
   12 | #define s second
      |           ^
teams.cpp:57:32: note: in expansion of macro 's'
   57 | void init(int _n, int f[], int s[]) {
      |                                ^
teams.cpp:12:11: note: shadowed declaration is here
   12 | #define s second
      |           ^~~~~~
teams.cpp:15:15: note: in expansion of macro 's'
   15 | int L[K],R[K],s[K];
      |               ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:12:11: warning: declaration of 'second' shadows a global declaration [-Wshadow]
   12 | #define s second
      |           ^~~~~~
teams.cpp:76:7: note: in expansion of macro 's'
   76 |   int s=0; forn(i,m) s+=k[i];
      |       ^
teams.cpp:12:11: note: shadowed declaration is here
   12 | #define s second
      |           ^~~~~~
teams.cpp:15:15: note: in expansion of macro 's'
   15 | int L[K],R[K],s[K];
      |               ^
teams.cpp:87:15: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   87 |   int t=z.size();
      |         ~~~~~~^~

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