oj.uz

답안 #799594

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
799594 2023-07-31T16:21:49 Z I_Love_EliskaM_ 팀들 (IOI15_teams) C++14
100 / 100
 594 ms 156576 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 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 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 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 0 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 31464 KB Output is correct
2 Correct 59 ms 31688 KB Output is correct
3 Correct 49 ms 31472 KB Output is correct
4 Correct 51 ms 31520 KB Output is correct
5 Correct 26 ms 28756 KB Output is correct
6 Correct 25 ms 28756 KB Output is correct
7 Correct 25 ms 28756 KB Output is correct
8 Correct 25 ms 28756 KB Output is correct
9 Correct 25 ms 28536 KB Output is correct
10 Correct 24 ms 28580 KB Output is correct
11 Correct 24 ms 28560 KB Output is correct
12 Correct 25 ms 28652 KB Output is correct
13 Correct 31 ms 28832 KB Output is correct
14 Correct 33 ms 29952 KB Output is correct
15 Correct 42 ms 31164 KB Output is correct
16 Correct 43 ms 31128 KB Output is correct
17 Correct 27 ms 28756 KB Output is correct
18 Correct 27 ms 28804 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 31424 KB Output is correct
2 Correct 53 ms 31488 KB Output is correct
3 Correct 117 ms 31448 KB Output is correct
4 Correct 48 ms 31468 KB Output is correct
5 Correct 69 ms 28756 KB Output is correct
6 Correct 60 ms 28768 KB Output is correct
7 Correct 31 ms 28740 KB Output is correct
8 Correct 53 ms 28740 KB Output is correct
9 Correct 25 ms 28632 KB Output is correct
10 Correct 26 ms 28616 KB Output is correct
11 Correct 30 ms 28636 KB Output is correct
12 Correct 63 ms 28620 KB Output is correct
13 Correct 97 ms 28764 KB Output is correct
14 Correct 105 ms 30968 KB Output is correct
15 Correct 69 ms 31164 KB Output is correct
16 Correct 75 ms 31180 KB Output is correct
17 Correct 46 ms 28848 KB Output is correct
18 Correct 48 ms 28764 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 413 ms 156392 KB Output is correct
2 Correct 430 ms 156456 KB Output is correct
3 Correct 581 ms 156376 KB Output is correct
4 Correct 401 ms 156576 KB Output is correct
5 Correct 292 ms 142252 KB Output is correct
6 Correct 250 ms 142284 KB Output is correct
7 Correct 139 ms 142236 KB Output is correct
8 Correct 232 ms 142268 KB Output is correct
9 Correct 116 ms 141252 KB Output is correct
10 Correct 120 ms 141288 KB Output is correct
11 Correct 150 ms 141316 KB Output is correct
12 Correct 214 ms 141396 KB Output is correct
13 Correct 355 ms 143116 KB Output is correct
14 Correct 594 ms 153924 KB Output is correct
15 Correct 357 ms 153100 KB Output is correct
16 Correct 351 ms 153040 KB Output is correct
17 Correct 174 ms 142492 KB Output is correct
18 Correct 169 ms 142532 KB Output is correct