Submission #541052

#TimeUsernameProblemLanguageResultExecution timeMemory
541052GioChkhaidzeTeams (IOI15_teams)C++14
0 / 100
1082 ms149508 KiB
#include <bits/stdc++.h> #include "teams.h" #define lf (h << 1) #define mf ((l + r) >> 1) #define rf ((h << 1) | 1) #define tree int h, int l, int r #define left lf, l, mf #define right rf, mf + 1, r #define ll long long #define pb push_back #define f first #define s second using namespace std; const int Nn = 5e5 + 5; bool used[Nn]; int n, m, cost, a[Nn], b[Nn], k[Nn], dp[Nn], pr[Nn], nx[Nn], mpr[Nn]; vector < int > v[4* Nn], O[Nn]; void build(tree) { if (l == r) { v[h] = O[l]; return; } build(left), build(right); int li = 0, ri = 0, ls = v[lf].size(), rs = v[rf].size(); while (li < ls || ri < rs) { if (li < ls && (ri == rs || v[lf][li] <= v[rf][ri])) { v[h].pb(v[lf][li++]); } else if (ri < rs && (li == ls || v[rf][ri] <= v[lf][li])) { v[h].pb(v[rf][ri++]); } } } int Mn, Mx, id; int g(int h) { int l = (lower_bound(v[h].begin(), v[h].end(), Mn - 1) - v[h].begin()); int r = (lower_bound(v[h].begin(), v[h].end(), Mx + 1) - v[h].begin()); return r - l; } int get(tree) { if (l == r) return g(h); if (Mx <= mf) return get(left) + g(rf); return get(right); } int Get(tree, int vl) { if (l == r) { if (vl <= g(h)) return l; return n + 1; } int rc = g(rf); if (rc < vl) return Get(left, vl - rc); return Get(right, vl); } int Mm(int l, int r) { Mn = k[l] + 1, Mx = k[r]; if (Mn > Mx) return n + 1; return Get(1, 1, n, dp[r] - dp[l]); } /* i < j dp[i] + solve(i, k) <= dp[j] + solve(j, k); dp[j] - dp[i] >= solve(i, k) - solve(j, k) mid = {k[j] + 1, n} dp[j] - dp[i] >= solve(i, mid) - solve(j, mid) max number of a,b such that a in (k[i] + 1, k[j]) b in (k[mid], n) how many a,b a in (k[i] + 1, k[k]) b in (k[k], n) how many a,b a in (k[j] + 1, k[k]) b in (k[k], n) */ void init(int N, int A[], int B[]) { n = N; for (int i = 1; i <= n; ++i) { a[i] = A[i - 1]; b[i] = B[i - 1]; O[b[i]].pb(a[i]); } for (int i = 1; i <= n; ++i) { sort(O[i].begin(), O[i].end()); } build(1, 1, n); } int can(int M, int K[]) { m = M; ll sum = 0; for (int i = 1; i <= m; ++i) { used[i] = false; k[i] = K[i - 1]; sum += k[i]; } sort(k + 1, k + m + 1); if (sum > n) return 0; set < pair < int , int > > st; vector < int > dq; dq.push_back(0); // get(1, 1, n); // how many a,b a in (k[l] + 1, k[i]) b in (k[i], n) for (int i = 1; i <= m; ++i) { while (st.size() && (*st.begin()).f <= k[i]) { int mo = (*st.begin()).f; int id = (*st.begin()).s; st.erase(st.find({mo, id})); used[id] = true; // was erased pr[id] -> id int tl = pr[id], tr = nx[id]; if (tr) { // erase id -> nx[id] st.erase({mpr[tr], tr}); mpr[tr] = Mm(tl, tr); // insert pr[id] -> nx[id] st.insert({mpr[tr], tr}); nx[tl] = tr, pr[tr] = tl; } } // find dp[i]; while (used[dq.back()]) { dq.pop_back(); } int l = dq.back(); Mn = k[l] + 1, Mx = k[i]; if (Mn <= Mx) cost = get(1, 1, n); else cost = 0; dp[i] = dp[l] - k[i] + cost; if (dp[i] < 0) return false; dq.push_back(i); mpr[i] = Mm(l, i); pr[i] = l, nx[l] = i; st.insert({mpr[i], i}); } return true; }

Compilation message (stderr)

teams.cpp: In function 'void build(int, int, int)':
teams.cpp:29:38: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   29 |  int li = 0, ri = 0, ls =  v[lf].size(), rs = v[rf].size();
      |                            ~~~~~~~~~~^~
teams.cpp:29:57: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   29 |  int li = 0, ri = 0, ls =  v[lf].size(), rs = v[rf].size();
      |                                               ~~~~~~~~~~^~
teams.cpp: In function 'int g(int)':
teams.cpp:44:57: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   44 |  int l = (lower_bound(v[h].begin(), v[h].end(), Mn - 1) - v[h].begin());
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
teams.cpp:45:57: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   45 |  int r = (lower_bound(v[h].begin(), v[h].end(), Mx + 1) - v[h].begin());
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:120:8: warning: declaration of 'id' shadows a global declaration [-Wshadow]
  120 |    int id = (*st.begin()).s;
      |        ^~
teams.cpp:41:13: note: shadowed declaration is here
   41 | int Mn, Mx, id;
      |             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...