oj.uz

Submission #990291

# Submission time Handle Problem Language Result Execution time Memory
990291 2024-05-30T06:12:59 Z VinhLuu Teams (IOI15_teams) C++17
100 / 100
 1758 ms 166164 KB 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 5e5 + 5;
int block = 555;
const int mod = 1e9 + 7;
//const ll oo = 5e18;

int n, cnt, R[N], m;

struct NODE{
   int l, r, w;
} st[N * 25];

int Newchild(int val){
   cnt++;
   st[cnt].w = val;
   st[cnt].l = st[cnt].r = 0;
   return cnt;
}

int Newnode(int l,int r){
   cnt++;
   st[cnt].l = l, st[cnt].r = r;
   st[cnt].w = st[l].w + st[r].w;
   return cnt;
}

int build(int l,int r){
   if(l == r) return Newchild(0);
   int mid = (l + r) / 2;
   return Newnode(build(l, mid), build(mid + 1, r));
}

int update(int i,int l,int r,int u){
   if(l > u || r < u) return i;
   if(l == r) return Newchild(st[i].w + 1);
   int mid = (l + r) / 2;
   return Newnode(update(st[i].l, l, mid, u), update(st[i].r, mid + 1, r, u));
}

int get(int i,int l,int r,int u,int v){
   if(l > r || l > v || r < u) return 0;
   if(u <= l && r <= v) return st[i].w;
   int mid = (l + r) / 2;
   return get(st[i].l, l, mid, u, v) + get(st[i].r, mid + 1, r, u, v);
}
vector<int> add[N];
int sign[N];
void init(int _n, int A[], int B[]){
   n = _n;
   m = 0;
   vector<int> vr;
   for(int i = 0; i < n; i ++) vr.pb(i);
   sort(all(vr), [&] (int x,int y){return (B[x] == B[y] ? A[x] < A[y] : B[x] < B[y]);});
   int ptr = 0;

   for(int i = 1; i <= n + 1; i ++) sign[i] = n + 1;
   for(int i = n - 1; i >= 0; i --){
//      cerr << B[vr[i]] << " ";
      sign[B[vr[i]]] = i + 1;
      B[vr[i]] = i + 1;
   }
//   cerr << "\n";
   for(int i = n; i >= 1; i --){
      sign[i] = min(sign[i + 1], sign[i]);
   }
   for(int i = 0; i < n; i ++){
      add[A[i]].pb(B[i]);
   }

   R[0] = build(1, n);
   for(int i = 1; i <= n; i ++){
      int cur = R[i - 1], tmp = 0;
      for(auto j : add[i]){
         tmp = update(cur, 1, n, j);
         swap(tmp, cur);
      }
      R[i] = cur;
   }
}

ll mark[N], sub;
vector<int> K;
vector<pii> sk;

ll cal(int i,int mid){
   if(mid == 0) return 0;
   ll val = get(R[K[i]], 1, n, 1, mid);
   if(sk.empty()) val -= sub;
   else if(sk[0].fi <= mid) val -= sub;
   else{
      int le = 0, ri = sk.size() - 1, mi, u = -1;
      while(le <= ri){mi = (le + ri) / 2;
         if(sk[mi].fi >= mid) u = mi, le = mi + 1; else ri = mi - 1;}

      int lef = (u == sk.size() - 1 ? 1 : sk[u + 1].fi + 1);
      val = val - (sub - mark[sk[u].se] + get(R[K[sk[u].se]], 1, n, lef, mid));
   }
   return val;
}

int can(int M,int k[]){
   K.clear(), sk.clear();
   int sum = 0;
   for(int i = 0; i < M; i ++){
      mark[i] = 0, K.pb(k[i]);
      sum += k[i];
   }
   sort(all(K));
   if(K.back() > n || sum > n) return 0;

   sub = 0;

   for(int i = 0; i < M; i ++){
      int l = sign[K[i]], r = n, mid, ans = -1;
      ll w = cal(i, sign[K[i]] - 1);
      while(l <= r){
         mid = (l + r) / 2;
         ll val = cal(i, mid) - w;
         if(val >= K[i]){
            ans = mid;
            r = mid - 1;
         }else l = mid + 1;
      }
      if(ans == -1) return 0;
      int tmp = 1; bool gg = 0;
      while(!sk.empty() && sk.back().fi <= ans){
         sub = sub - get(R[K[sk.back().se]], 1, n, tmp, sk.back().fi);
         tmp = sk.back().fi + 1;
         gg = 1;
         sk.pop_back();
      }
      if(!sk.empty() && gg){
         mark[sk.back().se] += get(R[K[sk.back().se]], 1, n, 1, tmp - 1);
         sub += get(R[K[sk.back().se]], 1, n, 1, tmp - 1);
      }

      if(!sk.empty()){
         int lmao = get(R[K[sk.back().se]], 1, n, 1, ans);
         mark[sk.back().se] -= lmao;
         sub -= lmao;
      }
      mark[i] = get(R[K[i]], 1, n, 1, ans) + (sk.empty() ? 0 : mark[sk.back().se]);
      sub += get(R[K[i]], 1, n, 1, ans);
      sk.pb({ans, i});
   }

   return 1;

}

Compilation message

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:66:8: warning: unused variable 'ptr' [-Wunused-variable]
   66 |    int ptr = 0;
      |        ^~~
teams.cpp: In function 'long long int cal(int, int)':
teams.cpp:103:34: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  103 |       int le = 0, ri = sk.size() - 1, mi, u = -1;
      |                        ~~~~~~~~~~^~~
teams.cpp:107:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |       int lef = (u == sk.size() - 1 ? 1 : sk[u + 1].fi + 1);
      |                  ~~^~~~~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 3 ms 16844 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 2 ms 16816 KB Output is correct
6 Correct 3 ms 16988 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 3 ms 16732 KB Output is correct
9 Correct 3 ms 16732 KB Output is correct
10 Correct 3 ms 16872 KB Output is correct
11 Correct 3 ms 16732 KB Output is correct
12 Correct 4 ms 16876 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Correct 3 ms 16732 KB Output is correct
15 Correct 2 ms 16728 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 3 ms 16732 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 2 ms 16732 KB Output is correct
20 Correct 3 ms 16732 KB Output is correct
21 Correct 3 ms 16728 KB Output is correct
22 Correct 3 ms 16732 KB Output is correct
23 Correct 2 ms 16732 KB Output is correct
24 Correct 2 ms 16732 KB Output is correct
25 Correct 2 ms 16732 KB Output is correct
26 Correct 2 ms 16732 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 42700 KB Output is correct
2 Correct 45 ms 42692 KB Output is correct
3 Correct 47 ms 42700 KB Output is correct
4 Correct 49 ms 45892 KB Output is correct
5 Correct 31 ms 41676 KB Output is correct
6 Correct 30 ms 41672 KB Output is correct
7 Correct 29 ms 41684 KB Output is correct
8 Correct 29 ms 41540 KB Output is correct
9 Correct 106 ms 43560 KB Output is correct
10 Correct 54 ms 41296 KB Output is correct
11 Correct 29 ms 41308 KB Output is correct
12 Correct 25 ms 41352 KB Output is correct
13 Correct 32 ms 41680 KB Output is correct
14 Correct 35 ms 42188 KB Output is correct
15 Correct 43 ms 42440 KB Output is correct
16 Correct 43 ms 42600 KB Output is correct
17 Correct 30 ms 41420 KB Output is correct
18 Correct 32 ms 41600 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 42700 KB Output is correct
2 Correct 52 ms 42696 KB Output is correct
3 Correct 313 ms 45548 KB Output is correct
4 Correct 47 ms 45892 KB Output is correct
5 Correct 280 ms 41672 KB Output is correct
6 Correct 254 ms 41680 KB Output is correct
7 Correct 35 ms 41684 KB Output is correct
8 Correct 196 ms 41684 KB Output is correct
9 Correct 92 ms 43716 KB Output is correct
10 Correct 195 ms 41420 KB Output is correct
11 Correct 218 ms 41564 KB Output is correct
12 Correct 292 ms 41364 KB Output is correct
13 Correct 387 ms 41788 KB Output is correct
14 Correct 402 ms 44096 KB Output is correct
15 Correct 202 ms 42816 KB Output is correct
16 Correct 192 ms 42564 KB Output is correct
17 Correct 201 ms 41464 KB Output is correct
18 Correct 191 ms 41464 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 161476 KB Output is correct
2 Correct 379 ms 161472 KB Output is correct
3 Correct 1444 ms 166164 KB Output is correct
4 Correct 362 ms 163612 KB Output is correct
5 Correct 870 ms 155332 KB Output is correct
6 Correct 717 ms 155476 KB Output is correct
7 Correct 170 ms 155588 KB Output is correct
8 Correct 600 ms 155584 KB Output is correct
9 Correct 641 ms 156028 KB Output is correct
10 Correct 609 ms 154508 KB Output is correct
11 Correct 698 ms 154460 KB Output is correct
12 Correct 957 ms 156312 KB Output is correct
13 Correct 1290 ms 156100 KB Output is correct
14 Correct 1758 ms 161912 KB Output is correct
15 Correct 713 ms 159824 KB Output is correct
16 Correct 716 ms 159684 KB Output is correct
17 Correct 584 ms 155328 KB Output is correct
18 Correct 571 ms 155588 KB Output is correct