Submission #780904

#TimeUsernameProblemLanguageResultExecution timeMemory
780904caganyanmazTeams (IOI15_teams)C++17
100 / 100
3997 ms140900 KiB
#include <bits/stdc++.h> #define pb push_back using namespace std; #define mp(x...) array<int, 2>({x}) #include "teams.h" constexpr static int DEBUG_SIZE = 10; void __print(size_t i) { cerr << i; } void __print(const char* s) { cerr << s; } void __print(string s) { cerr << s; } void __print(int* i) { cerr << "{"; cerr << i[0]; for (int j = 1; j < DEBUG_SIZE; j++) cerr << ", " << i[j]; cerr << "}"; } void __print(int i) { cerr << i; } template<typename T> void __print(T& t) {cerr <<"{";int f = 0; for (auto& i : t) { cerr << ((f++) ? ", ": ""); __print(i); } cerr <<"}";} void _print() { cerr << "]\n"; } template<typename T, typename... V> void _print(T t, V... v) { __print(t); if(sizeof...(v)) cerr << ", "; _print(v...); } //#define DEBUGGING #ifdef DEBUGGING #define debug(x...) cerr << "[" << (#x) << "] = ["; _print(x) #else #define debug(x...) #endif constexpr static int MXSIZE = 1e6; constexpr static int MXSEG = 1e8; int n, st[MXSEG], l[MXSEG], r[MXSEG]; array<int, 2> intervals[MXSIZE]; array<int, 2> updates[MXSIZE+1]; int last = 1; int query(int ll, int rr, int index, int ss, int ee) { if (ll >= ee || ss >= rr || index == -1) return 0; if (ee >= rr && ll >= ss) return st[index]; int m = ll+rr>>1; int lres = query(ll, m, l[index], ss, ee); int rres = query(m, rr, r[index], ss, ee); return lres + rres; } int update(int ll, int rr, int index, int i, int val) { if (ll + 1 == rr) { st[last] = val; return last++; } int m = ll+rr>>1; int lindex, rindex; if (i < m) { lindex = update(ll, m, l[index], i, val); rindex = (index == -1) ? -1 : r[index]; } else { lindex = (index == -1) ? -1 : l[index]; rindex = update(m, rr, r[index], i, val); } l[last] = lindex; r[last] = rindex; st[last] = (lindex == -1) ? 0 : st[lindex]; st[last] += (rindex == -1) ? 0 : st[rindex]; return last++; } void config_st() { l[0] = r[0] = -1; } void init(int N, int A[], int B[]) { n = N; for (int i = 0; i < n; i++) intervals[i] = mp(A[i], B[i]); sort(intervals, intervals + n); int last_root = 0; updates[0] = mp(0, 0); for (int i = 0; i < n; i++) { int old_count = query(0, n, last_root, intervals[i][1]-1, intervals[i][1]); int new_root = update(0, n, last_root, intervals[i][1]-1, old_count+1); updates[i+1] = mp(intervals[i][0], new_root); debug(i+1, intervals[i][0], new_root); last_root = new_root; } } int can(int m, int k[]) { sort(k, k+m); vector<array<int, 2>> teams; for (int i = 0; i < m; i++) { if (!teams.size() || end(teams)[-1][0] != k[i]) teams.pb(mp(k[i], 0)); end(teams)[-1][1]++; } debug(teams.size()); vector<array<int, 3>> stck; // Root, ending, additional (if at there are some free left in the ending) for (int i = 0; i < teams.size(); i++) { int current_index = upper_bound(updates, updates + n, mp(teams[i][0] + 1, -1)) - updates; if (teams[i][0] + 1 > updates[current_index][0]) current_index++; if (!current_index) return 0; current_index--; int current_root = updates[current_index][1]; int current_val = teams[i][0] * teams[i][1]; int last_l = teams[i][0] - 1; debug(teams[i][0], teams[i][1], current_val, current_root, last_l); while (stck.size()) { if (last_l < end(stck)[-1][1]) { debug("hi"); int prev_used = query(0, n, end(stck)[-1][0], last_l, end(stck)[-1][1]) - end(stck)[-1][2]; int current_available = query(0, n, current_root, last_l, end(stck)[-1][1]); if (current_val + prev_used <= current_available) break; current_val += prev_used - current_available; last_l = end(stck)[-1][1]; } stck.pop_back(); } int ending = n+1; if (stck.size()) ending = end(stck)[-1][1]+1; int ll = last_l, rr = ending; debug(last_l, ending, current_val); while (rr - ll > 1) { int m = ll+rr>>1; int val = query(0, n, current_root, last_l, m); if (stck.size()) { val -= query(0, n, end(stck)[-1][0], last_l, m); if (m == end(stck)[-1][1]) val += end(stck)[-1][2]; } if (val >= current_val) rr = m; else ll = m; } if (rr == ending) return 0; debug(current_root, last_l, rr, query(0, n, current_root, last_l, rr), query(0, n, current_root, 0, n)); int last_val = query(0, n, current_root, last_l, rr); if (stck.size()) { last_val -= query(0, n, end(stck)[-1][0], last_l, rr); if (rr == end(stck)[-1][1]) last_val += end(stck)[-1][2]; } stck.pb({current_root, rr, last_val - current_val}); debug(stck); } return 1; }

Compilation message (stderr)

teams.cpp: In function 'int query(int, int, int, int, int)':
teams.cpp:39:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         int m = ll+rr>>1;
      |                 ~~^~~
teams.cpp: In function 'int update(int, int, int, int, int)':
teams.cpp:52:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         int m = ll+rr>>1;
      |                 ~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:106:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for (int i = 0; i < teams.size(); i++)
      |                         ~~^~~~~~~~~~~~~~
teams.cpp:108:96: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  108 |                 int current_index = upper_bound(updates, updates + n, mp(teams[i][0] + 1, -1)) - updates;
      |                                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
teams.cpp:139:29: warning: declaration of 'int m' shadows a parameter [-Wshadow]
  139 |                         int m = ll+rr>>1;
      |                             ^
teams.cpp:94:13: note: shadowed declaration is here
   94 | int can(int m, int k[])
      |         ~~~~^
teams.cpp:139:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  139 |                         int m = ll+rr>>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...