Submission #795693

#	Time	Username	Problem	Language	Result	Execution time	Memory
795693		I_Love_EliskaM_	Teams (IOI15_teams)	C++14	77 / 100	4077 ms	245732 KiB

teams

#include "teams.h"
#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 len = 1.3e7 + 5;
int sum[len], ls[len], rs[len], l[len], r[len], cnt = 0;
int build(int li, int ri)
{
  int vr = cnt++;
  l[vr] = li, r[vr] = ri, sum[vr] = 0;
  if (li != ri) ls[vr] = build(li, (li + ri) / 2), rs[vr] = build((li + ri) / 2 + 1, ri);
  return vr;
}
int upd(int i, int vr) // vrati novy koren
{
  if (i < l[vr] || i > r[vr]) return vr;
  int v2 = cnt++;
  sum[v2] = sum[vr] + 1;
  l[v2] = l[vr], r[v2] = r[vr];
  if (l[vr] != r[vr]) ls[v2] = upd(i, ls[vr]), rs[v2] = upd(i, rs[vr]);
  return v2;
}
int query(int li, int ri, int vr)
{
  if (ri < l[vr] || li > r[vr]) return 0;
  if (li <= l[vr] && r[vr] <= ri) return sum[vr];
  return query(li, ri, ls[vr]) + query(li, ri, rs[vr]);
}
int st[(int)5e5+5];

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]=build(0,n);
  for(int i=n; i>0; --i) {
    st[i]=st[i+1];
    for(auto&x:v[i]) {
      st[i]=upd(a[x].f,st[i]);
    }
  } 
}

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) {
    forn(j,i+1) {
      int cnt;
      if (j==0) {
        cnt=query(0,z[i].f,st[z[i].f]);
      } else {
        cnt=query(z[j-1].f+1,z[i].f,st[z[i].f]);
      }
      dp[i+1]=max(dp[i+1],dp[j]+z[i].f*z[i].s-cnt);
    }
    if (dp[i+1]>0) return 0;
  }
  return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:70:15: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   70 |   int t=z.size();
      |         ~~~~~~^~
teams.cpp:77:11: warning: declaration of 'cnt' shadows a global declaration [-Wshadow]
   77 |       int cnt;
      |           ^~~
teams.cpp:13:49: note: shadowed declaration is here
   13 | int sum[len], ls[len], rs[len], l[len], r[len], cnt = 0;
      |                                                 ^~~

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