Submission #1033114

#TimeUsernameProblemLanguageResultExecution timeMemory
1033114socpiteTeams (IOI15_teams)C++17
100 / 100
1358 ms524288 KiB
#include "teams.h" #include<bits/stdc++.h> using namespace std; const int maxn = 5e5+5; const long long INF = 1e18; const int blsz = 100; vector<int> FW[maxn]; vector<int> d[maxn]; int pfx_all[maxn], sfx_all[maxn]; int L[maxn], R[maxn]; int dp[maxn]; vector<int> precalc[maxn]; vector<int> pos[maxn]; map<pair<int, int>, int> mp; int n; struct node{ node *lc, *rc; int sum; node(int _sum = 0): sum(_sum), lc(nullptr), rc(nullptr){}; void build(int l = 1, int r = n){ if(l == r)return; lc = new node(); rc = new node(); int mid = (l+r)>>1; lc->build(l, mid); rc->build(mid+1, r); } void upd(node &old_tree, int pos, int l = 1, int r = n){ sum = old_tree.sum + 1; if(l == r)return; int mid = (l+r)>>1; if(pos <= mid){ rc = old_tree.rc; lc = new node(); lc->upd(*old_tree.lc, pos, l, mid); } else { lc = old_tree.lc; rc = new node(); rc->upd(*old_tree.rc, pos, mid+1, r); } } int query(int pos, int l = 1, int r = n){ if(l == r)return sum; int mid = (l+r)>>1; if(pos <= mid)return lc->query(pos, l, mid); else return rc->query(pos, mid+1, r) + lc->sum; } }; vector<node> rt; int rtpos[maxn]; int gt(int a, int b){ if(b == 0)return 0; return rt[rtpos[a]].query(b); } int gt_gap(int l, int r){ if(l > r)return 0; if(r-l < precalc[l].size())return precalc[l][r-l]; int re = pfx_all[r] - gt(r, l-1); return re; } void init(int N, int A[], int B[]) { n = N; for(int i = 0; i < n; i++){ L[i] = A[i]; R[i] = B[i]; pos[R[i]].push_back(L[i]); for(int x = B[i]; x <= n; x += x&(-x))d[x].push_back(A[i]); pfx_all[B[i]]++; sfx_all[A[i]]++; } for(int i = 1; i <= n; i++){ pfx_all[i] += pfx_all[i-1]; sort(pos[i].begin(), pos[i].end()); d[i].push_back(-1); sort(d[i].begin(), d[i].end()); d[i].erase(unique(d[i].begin(), d[i].end()), d[i].end()); FW[i].assign(d[i].size(), 0); } for(int i = 1; i <= n; i++){ int crr = 0; for(int j = 0; j + i <= n && j < n/i; j++){ crr += pos[i+j].end() - lower_bound(pos[i+j].begin(), pos[i+j].end(), i); precalc[i].push_back(crr); } } for(int i = n; i >= 1; i--)sfx_all[i] += sfx_all[i+1]; rt.push_back(node()); rt.back().build(); for(int i = 1; i <= n; i++){ for(auto v: pos[i]){ node nw; nw.upd(rt.back(), v); rt.push_back(nw); } rtpos[i] = rt.size()-1; } for(int i = 1; i <= n; i++){ for(int j = 1; j < FW[i].size(); j++)FW[i][j] += FW[i][j-1]; } } int can(int M, int K[]) { long long sum = 0; sort(K, K+M); vector<pair<int, int>> vec; for(int i = 0; i < M; i++){ sum += K[i]; if(vec.empty() || vec.back().first != K[i])vec.push_back({K[i], 1}); else vec.back().second++; } if(sum > n)return 0; for(int i = 0; i < vec.size(); i++){ dp[i] = vec[i].first*vec[i].second + pfx_all[vec[i].first-1]; for(int j = 0; j < i; j++){ dp[i] = max(dp[i], dp[j] + vec[i].first*vec[i].second + gt_gap(vec[j].first+1,vec[i].first-1)); } sum -= vec[i].first*vec[i].second; if(dp[i] + sum > n)return 0; if(dp[i] + sfx_all[vec[i].first+1] > n)return 0; } return 1; // sum_segment - sum_M < 0 => bad // sum_segment = pfx_all - sumgap }

Compilation message (stderr)

teams.cpp: In constructor 'node::node(int)':
teams.cpp:25:6: warning: 'node::sum' will be initialized after [-Wreorder]
   25 |  int sum;
      |      ^~~
teams.cpp:24:8: warning:   'node* node::lc' [-Wreorder]
   24 |  node *lc, *rc;
      |        ^~
teams.cpp:26:2: warning:   when initialized here [-Wreorder]
   26 |  node(int _sum = 0): sum(_sum), lc(nullptr), rc(nullptr){};
      |  ^~~~
teams.cpp: In member function 'void node::upd(node&, int, int, int)':
teams.cpp:35:31: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
   35 |  void upd(node &old_tree, int pos, int l = 1, int r = n){
      |                           ~~~~^~~
teams.cpp:17:13: note: shadowed declaration is here
   17 | vector<int> pos[maxn];
      |             ^~~
teams.cpp: In member function 'int node::query(int, int, int)':
teams.cpp:50:16: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
   50 |  int query(int pos, int l = 1, int r = n){
      |            ~~~~^~~
teams.cpp:17:13: note: shadowed declaration is here
   17 | vector<int> pos[maxn];
      |             ^~~
teams.cpp: In function 'int gt_gap(int, int)':
teams.cpp:68:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  if(r-l < precalc[l].size())return precalc[l][r-l];
      |     ~~~~^~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:95:75: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   95 |    crr += pos[i+j].end() - lower_bound(pos[i+j].begin(), pos[i+j].end(), i);
      |                                                                           ^
teams.cpp:110:23: warning: conversion from 'std::vector<node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  110 |   rtpos[i] = rt.size()-1;
      |              ~~~~~~~~~^~
teams.cpp:114:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for(int j = 1; j < FW[i].size(); j++)FW[i][j] += FW[i][j-1];
      |                  ~~^~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:128:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |  for(int i = 0; i < vec.size(); i++){
      |                 ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...