Submission #990268

#	Time	Username	Problem	Language	Result	Execution time	Memory
990268		VinhLuu	Teams (IOI15_teams)	C++17	13 / 100	1767 ms	168444 KiB

teams

//#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 --){
      sign[B[vr[i]]] = i + 1;
      B[vr[i]] = i + 1;
   }
   for(int i = n; i >= 1; i --){
      sign[i] = min(sign[i + 1], sign[i]);
//      cerr << i << " " << sign[i] << " l\n";
   }
   for(int i = 0; i < n; i ++){
//      cerr << i << " " << B[i] << " k\n";
      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;
   }
//   for(int i = 1; i <= n; i ++){
//      cerr << i << " h\n";
//      for(int j = 1; j <= n; j ++){
//         cerr << get(R[i], 1, n, 1, j) << " ";
//      }
//      cerr << "\n";
//   }
}

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

int cal(int i,int mid){
   if(mid == 0) return 0;
   int val = get(R[K[i]], 1, n, 1, mid);
   if(sk.empty() || 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();
   for(int i = 0; i < M; i ++) mark[i] = 0, K.pb(k[i]);
   sort(all(K));
   if(K.back() > n) return 0;

   sub = 0;

   for(int i = 0; i < M; i ++){
      int l = sign[K[i]], r = n, mid, ans = -1;
      int w = cal(i, sign[K[i]] - 1);
//      cerr << i << " " << w << " " << sub << " " << K[i] << " o\n";
//      for(auto j : sk) cerr << j.fi << " " << j.se << " " << mark[j.se] << " sk\n";

      while(l <= r){
         mid = (l + r) / 2;
         int val = cal(i, mid) - w;
//         cerr << mid << " " << val << " kt\n";
         if(val >= K[i]){
            ans = mid;
            r = mid - 1;
         }else l = mid + 1;
      }
//      cerr << i << " " << ans << " y\n";
      if(ans == -1) return 0;
      int tmp = 1;
      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;
         sk.pop_back();
      }

      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 (stderr)

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 'int cal(int, int)':
teams.cpp:109:34: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  109 |       int le = 0, ri = sk.size() - 1, mi, u = -1;
      |                        ~~~~~~~~~~^~~
teams.cpp:113: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]
  113 |       int lef = (u == sk.size() - 1 ? 1 : sk[u + 1].fi + 1);
      |                  ~~^~~~~~~~~~~~~~~~

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