제출 #541190

#제출 시각아이디문제언어결과실행 시간메모리
541190NachoLibre팀들 (IOI15_teams)C++17
0 / 100
4083 ms30340 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define vint vector<int> using namespace std; #ifndef x #include "teams.h" #else #endif const int N = 500005, S = 200005; int n, a[N], b[N], m, k[S], dp[S]; vector<int> e[N]; struct zz { zz *l = 0, *r = 0; vector<int> v; vector<array<int, 2> > t, lv, rv; void P() { int li = 0, ri = 0; while(li < sz(l->v) || ri < sz(r->v)) { if(li == sz(l->v) || (ri < sz(r->v) && r->v[ri] < l->v[li])) { v.push_back(r->v[ri]); t.push_back({1, ri}); ri += 1; } else if(ri == sz(r->v) || r->v[ri] > l->v[li]) { v.push_back(l->v[li]); t.push_back({0, li}); li += 1; } } lv.resize(sz(v), {-1, -1}); rv.resize(sz(v), {-1, -1}); for(int i = 0; i < sz(v); ++i) { if(t[i][0] == 0) lv[i][0] = t[i][1]; else if(i) lv[i][0] = lv[i - 1][0]; if(t[i][0] == 1) rv[i][0] = t[i][1]; else if(i) rv[i][0] = rv[i - 1][0]; } for(int i = sz(v) - 1; i >= 0; --i) { if(t[i][0] == 0) lv[i][1] = t[i][1]; else if(i < sz(v) - 1) lv[i][1] = lv[i + 1][1]; if(t[i][0] == 1) rv[i][1] = t[i][1]; else if(i < sz(v) - 1) rv[i][1] = rv[i + 1][1]; } } void add(int x) { v.push_back(x); t.push_back({0, 0}); lv.push_back({0, 0}); rv.push_back({0, 0}); } } *root; void bld(int l = 1, int r = n + 1, zz *&t = root) { if(!t) t = new zz(); if(l == r) { for(int i = 0; i < sz(e[l]); ++i) { t->add(e[l][i]); } return; } int m = l + r >> 1; bld(l, m, t->l); bld(m + 1, r, t->r); t->P(); } int cnt(int vl, int vr, int sl, int l = 1, int r = n + 1, zz *&t = root) { if(!t || vl > vr || vl == -1 || vr == -1) { return 0; } if(r < sl) return 0; if(l >= sl) return vr - vl + 1; int m = l + r >> 1; return cnt(t->lv[vl][1], t->lv[vr][0], sl, l, m, t->l) + cnt(t->rv[vl][1], t->rv[vr][0], sl, m + 1, r, t->r); } int Z(int i, int j) { // [k[i] + 1, k[j]] x [k[j], +oo) int xl = (i == -1 ? 1 : k[i] + 1), xr = k[j], sl = k[j]; int vl = lower_bound(all(root->v), xl) - (root->v).begin(); int vr = int(upper_bound(all(root->v), xr) - (root->v).begin()) - 1; if(vl > vr) return 0; return cnt(vl, vr, sl); } void init(int _n, int _a[], int _b[]) { n = _n; for(int i = 0; i < n; ++i) { a[i] = _a[i]; b[i] = _b[i]; e[b[i]].push_back(a[i]); } for(int i = 1; i <= n; ++i) { sort(all(e[i])); } bld(); } array<int, 2> mir(int vl, int vr, int cr, int l = 1, int r = n + 1, zz *&t = root) { if(!t || vl > vr || vl == -1 || vr == -1) { vl = 1; vr = 0; } if(l == r) { int ncr = cr - (vr - vl + 1); if(ncr >= 0) return {l, ncr}; return {r + 1, cr}; } if(vr - vl + 1 <= cr) { return {l, cr - (vr - vl + 1)}; } int m = l + r >> 1; array<int, 2> x = mir(t->rv[vl][1], t->rv[vr][0], cr, m + 1, r, t->r); if(x[0] == m + 1) { } } int mindx(int i, int j) { /* int xl = (i == -1 ? 1 : k[i] + 1), xr = k[j]; int vl = lower_bound(all(root->v), xl) - (root->v).begin(); int vr = int(upper_bound(all(root->v), xr) - (root->v).begin()) - 1; int cr = dp[j] - dp[i]; int y = mir(vl, vr, cr)[0]; // dp[j] - dp[i] > [k[i] + 1, k[j]] x [y, +oo) */ // // // // // // // // if(dp[i] + Z(i, m) >= dp[j] + Z(j, m)) { return m + 1; } int l = 0, r = m; while(l < r) { int md = l + r >> 1; if(dp[i] + Z(i, md) < dp[j] + Z(j, md)) r = md; else l = md + 1; } return l; } multiset<int> sx; multiset<array<int, 2> > sy; void insert_51(int i) { int x = -1; if(sz(sx)) x = *(--sx.end()); sx.insert(i); if(x == -1) return; sy.insert({mindx(x, i), i}); } bool pop_51(int i) { if(!sz(sy) || (*sy.begin())[0] > i) { return 0; } int x = (*sy.begin())[1]; sy.erase(sy.begin()); auto it = sx.find(x); sx.erase(it++); if(it == sx.end()) return 1; int z = *(it--); sy.erase(sy.find({mindx(x, z), z})); int y = *it; sy.insert({mindx(y, z), z}); return 1; } int can(int _m, int _k[]) { m = _m; for(int i = 0; i < m; ++i) { dp[i] = 0; // // // // k[i] = _k[i]; } sort(k, k + m); dp[0] = Z(-1, 0) - k[0]; /// insert_51(0); int dr = dp[0]; for(int i = 1; i < m; ++i) { while(pop_51(i)); int x = *(--sx.end()); dp[i] = dp[x] + Z(x, i) - k[i]; dr = min(dr, dp[i]); } return dr >= 0; } #ifdef x int main() { ios::sync_with_stdio(0); cin.tie(0); return 0; } #endif

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp: In function 'void bld(int, int, zz*&)':
teams.cpp:65:6: warning: declaration of 'm' shadows a global declaration [-Wshadow]
   65 |  int m = l + r >> 1;
      |      ^
teams.cpp:14:20: note: shadowed declaration is here
   14 | int n, a[N], b[N], m, k[S], dp[S];
      |                    ^
teams.cpp:65:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |  int m = l + r >> 1;
      |          ~~^~~
teams.cpp: In function 'int cnt(int, int, int, int, int, zz*&)':
teams.cpp:75:6: warning: declaration of 'm' shadows a global declaration [-Wshadow]
   75 |  int m = l + r >> 1;
      |      ^
teams.cpp:14:20: note: shadowed declaration is here
   14 | int n, a[N], b[N], m, k[S], dp[S];
      |                    ^
teams.cpp:75:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |  int m = l + r >> 1;
      |          ~~^~~
teams.cpp: In function 'int Z(int, int)':
teams.cpp:82:41: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   82 |  int vl = lower_bound(all(root->v), xl) - (root->v).begin();
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'std::array<int, 2> mir(int, int, int, int, int, zz*&)':
teams.cpp:111:6: warning: declaration of 'm' shadows a global declaration [-Wshadow]
  111 |  int m = l + r >> 1;
      |      ^
teams.cpp:14:20: note: shadowed declaration is here
   14 | int n, a[N], b[N], m, k[S], dp[S];
      |                    ^
teams.cpp:111:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |  int m = l + r >> 1;
      |          ~~^~~
teams.cpp: In function 'int mindx(int, int)':
teams.cpp:132:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  132 |   int md = l + r >> 1;
      |            ~~^~~
teams.cpp: In function 'std::array<int, 2> mir(int, int, int, int, int, zz*&)':
teams.cpp:113:10: warning: control reaches end of non-void function [-Wreturn-type]
  113 |  if(x[0] == m + 1) {
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...