oj.uz

Submission #799603

# Submission time Handle Problem Language Result Execution time Memory
799603 2023-07-31T16:26:24 Z TimDee Teams (IOI15_teams) C++17
100 / 100
 635 ms 156468 KB 
#include "teams.h"
#pragma GCC optimize("O3")
#pragma target("avx2,bvx")
#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;
struct sgt {
  int l=0,r=0,s=0;
};
sgt t[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) {
    t[nxt].s=t[v].s+x;
    return nxt++;
  }
  int m=(l+r)>>1;
  if (i<m) {
    if (t[v].l==0) t[v].l=nxt++;
    int n = add(t[v].l,l,m,i,x);
    t[nxt].l=n, t[nxt].r=t[v].r, t[nxt].s=t[v].s+x;
    return nxt++;
  } else {
    if (t[v].r==0) t[v].r=nxt++;
    int n = add(t[v].r,m,r,i,x);
    t[nxt].l=t[v].l, t[nxt].r=n, t[nxt].s=t[v].s+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 t[v].s;
  int m=(l+r)>>1;
  int lq = t[v].l ? ( (lx>=m)?0:sum(t[v].l,l,m,lx,rx) ) : 0;
  int rq = t[v].r ? ( (rx<=m)?0:sum(t[v].r,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

teams.cpp:3: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    3 | #pragma target("avx2,bvx")
      | 
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:69:12: warning: declaration of 't' shadows a global declaration [-Wshadow]
   69 |       auto t=add(st[i],a[x].f,1);
      |            ^
teams.cpp:18:5: note: shadowed declaration is here
   18 | sgt t[K];
      |     ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:90:7: warning: declaration of 't' shadows a global declaration [-Wshadow]
   90 |   int t=z.size();
      |       ^
teams.cpp:18:5: note: shadowed declaration is here
   18 | sgt t[K];
      |     ^
teams.cpp:90:15: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   90 |   int t=z.size();
      |         ~~~~~~^~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31520 KB Output is correct
2 Correct 47 ms 31548 KB Output is correct
3 Correct 47 ms 31452 KB Output is correct
4 Correct 52 ms 31496 KB Output is correct
5 Correct 25 ms 28744 KB Output is correct
6 Correct 33 ms 28784 KB Output is correct
7 Correct 25 ms 28756 KB Output is correct
8 Correct 25 ms 28720 KB Output is correct
9 Correct 25 ms 28612 KB Output is correct
10 Correct 24 ms 28620 KB Output is correct
11 Correct 24 ms 28564 KB Output is correct
12 Correct 25 ms 28620 KB Output is correct
13 Correct 31 ms 28804 KB Output is correct
14 Correct 33 ms 29944 KB Output is correct
15 Correct 43 ms 31208 KB Output is correct
16 Correct 43 ms 31180 KB Output is correct
17 Correct 26 ms 28748 KB Output is correct
18 Correct 29 ms 28740 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 31512 KB Output is correct
2 Correct 52 ms 31500 KB Output is correct
3 Correct 104 ms 31528 KB Output is correct
4 Correct 48 ms 31436 KB Output is correct
5 Correct 70 ms 28800 KB Output is correct
6 Correct 60 ms 28844 KB Output is correct
7 Correct 34 ms 28708 KB Output is correct
8 Correct 54 ms 28716 KB Output is correct
9 Correct 31 ms 28572 KB Output is correct
10 Correct 27 ms 28632 KB Output is correct
11 Correct 29 ms 28600 KB Output is correct
12 Correct 64 ms 28620 KB Output is correct
13 Correct 108 ms 28784 KB Output is correct
14 Correct 121 ms 31000 KB Output is correct
15 Correct 68 ms 31140 KB Output is correct
16 Correct 71 ms 31164 KB Output is correct
17 Correct 46 ms 28752 KB Output is correct
18 Correct 48 ms 28820 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 156468 KB Output is correct
2 Correct 399 ms 156368 KB Output is correct
3 Correct 580 ms 156444 KB Output is correct
4 Correct 419 ms 156380 KB Output is correct
5 Correct 292 ms 142324 KB Output is correct
6 Correct 253 ms 142328 KB Output is correct
7 Correct 148 ms 142400 KB Output is correct
8 Correct 232 ms 142284 KB Output is correct
9 Correct 121 ms 141240 KB Output is correct
10 Correct 119 ms 141288 KB Output is correct
11 Correct 154 ms 141240 KB Output is correct
12 Correct 212 ms 141440 KB Output is correct
13 Correct 371 ms 143084 KB Output is correct
14 Correct 635 ms 153900 KB Output is correct
15 Correct 356 ms 153100 KB Output is correct
16 Correct 367 ms 153124 KB Output is correct
17 Correct 175 ms 142516 KB Output is correct
18 Correct 181 ms 142704 KB Output is correct