Submission #641809

#	Time	Username	Problem	Language	Result	Execution time	Memory
641809		QwertyPi	Teams (IOI15_teams)	C++14	100 / 100	1284 ms	238408 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define fi first
#define se second
 
using namespace std;
 
const int N = 5e5 + 11;
int n; 
int a[N], b[N];
int ed[N];
 
vector<pair<int, int>> stu;
 
 
namespace PerSeg{
 
	int id = 0;
	
	struct node{
		node(int _s = 0): s(_s), ll(0), rr(0) {};
		node(node* c, int ll, int rr) {
			if(c[ll].s == -1 || c[rr].s == -1)
				*this = c[ll].s == -1 ? c[rr] : c[ll];
			else {
				this->s = c[ll].s + c[rr].s;
				this->ll = ll, this->rr = rr;
			}
		}
		
		public:
			int s, ll, rr;
	};
 
	int root[N];
	node c[N * 30];
	
	int build(int l, int r){
		if(l == r){
			c[id] = node();
			return id++;
		}else{
			int tl = build(l, (l + r) / 2);
			int tr = build((l + r) / 2 + 1, r);
			c[id] = node(c, tl, tr);
			return id++;
		}
	}
 
	int add(int p, int v, int t, int l, int r){
		if(l == r){
			c[id] = node(c[t].s + v);
			return id++;
		}else{
			int m = (l + r) / 2;
			if(p <= m){
					int tl = add(p, v, c[t].ll, l, m);
					c[id] = node(c, tl, c[t].rr);
					return id++;
				}else{
					int tr = add(p, v, c[t].rr, m + 1, r);
					c[id] = node(c, c[t].ll, tr);
					return id++;
				}
		}
	}
 
	int qry(int t, int ql, int qr, int l, int r){
		if(r < ql || qr < l) return 0;
		if(ql <= l && r <= qr) return c[t].s;
		int m = (l + r) / 2;
		return qry(c[t].ll, ql, qr, l, m)
			+  qry(c[t].rr, ql, qr, m + 1, r);
	}
	
	void init(int n){
		root[0] = build(1, n);
		for(int i = 0; i < n; i++){
			root[i + 1] = add(stu[i].se, 1, root[i], 1, n);
		}
	}
 
	int qry(int l, int r, int y1, int y2){
		r = min(r, n);
		if(l > n || l > r) return 0;
		return qry(root[r], y1, y2, 1, n)
			 - qry(root[l], y1, y2, 1, n);
	}
 
	int qry_bs_(int l, int r, int pref, int tl, int tr){
		if(tl == tr){
			if(c[r].s - c[l].s > pref) return tl - 1;
			else return tl;
		}
		int tm = (tl + tr) / 2;
		int t = c[c[r].ll].s - c[c[l].ll].s;
		if(pref >= t){
			return qry_bs_(c[l].rr, c[r].rr, pref - t, tm + 1, tr);
		}else{
			return qry_bs_(c[l].ll, c[r].ll, pref, tl, tm);
		}
	}
	
	int qry_bs(int l, int r, int pref){
		return qry_bs_(root[l], root[r], pref, 1, n);
	}
};
 
namespace RMQ{
 
	int st[20][N];
	
	void init(int n, vector<int> a){
		for(int i = 0; i < n; i++){
			st[0][i] = a[i];
		}
		for(int j = 1; j < 20; j++){
			for(int i = 0; i <= n - (1 << j); i++){
				st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
			}
		}
	}
 
	int qry(int l, int r){
		if(l > r) return INT32_MAX;
		int d = __lg(r - l + 1);
		return min(st[d][l], st[d][r - (1 << d) + 1]);
	}
};
 
struct segment{
	int l, r, d = 0, c = 0; // [l, r)
 
	friend ostream& operator<< (ostream& out, const segment& a) {
		return out << "segment [" << a.l << ", " << a.r << "): " << "min = " << a.d << ", " << "minc = " << a.c << "\n";
	}
};
 
bool query(int k, vector<int>& s){
	int idx = 0;
	priority_queue<int, vector<int>, greater<int>> pq;
	vector<segment> vs;
	int cl = 0;
	vs.push_back({0, 0, N - 1, 0});
	int ccnt = 1;
	for(auto i : s){
		int cnt = 0;
		vs.push_back({cl, ed[i] + 1, RMQ::qry(cl, ed[i])}); cl = ed[i] + 1;
		while(vs.size() >= 2 && vs[vs.size() - 2].d < i){
			vs[vs.size() - 2].r = vs[vs.size() - 1].r;
			vs[vs.size() - 2].d = i;
			vs[vs.size() - 2].c = 0;
			vs.pop_back();
		}
		if(!vs.empty() && vs.back().d < i){
			vs.back().d = i;
			vs.back().c = 0;
		}
		while(vs.size() >= 2 && cnt < i){
			int val = PerSeg::qry(vs.back().l, vs.back().r, vs.back().d, vs[vs.size() - 2].d - 1) - vs.back().c;
			if(cnt + val <= i){
				cnt += val;
				vs[vs.size() - 2].r = vs[vs.size() - 1].r;
				vs.pop_back();
			}else{
				break;
			}
		}
		
		int rem = i - cnt;
		int pref = rem + vs.back().c + PerSeg::qry(vs.back().l, vs.back().r, 1, vs.back().d - 1);
		int h = PerSeg::qry_bs(vs.back().l, vs.back().r, pref);
		int v = PerSeg::qry(vs.back().l, vs.back().r, vs.back().d, h); 
		vs.back().d = h + 1;
		vs.back().c = rem + vs.back().c - v;
		int q = PerSeg::qry(vs.back().l, vs.back().r, h + 1, h + 1);
		if(q < rem - v)
			return 0;
	}
	return 1;
}
 
void init(int N, int A[], int B[]) {
  	n = N;
	for(int i = 0; i < n; i++){
		stu.push_back({A[i], B[i]});
	}
	sort(stu.begin(), stu.end());
 
	vector<int> stux;
	for(auto i : stu){
		stux.push_back(i.se);
	}
	RMQ::init(n, stux);
	
	fill(ed + 1, ed + n + 1, -1);
	for(int i = 0; i < n; i++){
		ed[stu[i].fi] = max(ed[stu[i].fi], i);
	}
	for(int i = 1; i <= n; i++){
		ed[i] = max(ed[i], ed[i - 1]);
	}
	
	PerSeg::init(n);
}
 
int can(int M, int K[]) {
	vector<int> s;
	for(int j = 0; j < M; j++){
		s.push_back(K[j]);
	}
	sort(s.begin(), s.end());
	return query(M, s);
}

Compilation message (stderr)

teams.cpp: In constructor 'PerSeg::node::node(PerSeg::node*, int, int)':
teams.cpp:22:29: warning: declaration of 'rr' shadows a member of 'PerSeg::node' [-Wshadow]
   22 |   node(node* c, int ll, int rr) {
      |                         ~~~~^~
teams.cpp:32:15: note: shadowed declaration is here
   32 |    int s, ll, rr;
      |               ^~
teams.cpp:22:21: warning: declaration of 'll' shadows a member of 'PerSeg::node' [-Wshadow]
   22 |   node(node* c, int ll, int rr) {
      |                 ~~~~^~
teams.cpp:32:11: note: shadowed declaration is here
   32 |    int s, ll, rr;
      |           ^~
teams.cpp: In constructor 'PerSeg::node::node(PerSeg::node*, int, int)':
teams.cpp:22:29: warning: declaration of 'rr' shadows a member of 'PerSeg::node' [-Wshadow]
   22 |   node(node* c, int ll, int rr) {
      |                         ~~~~^~
teams.cpp:32:15: note: shadowed declaration is here
   32 |    int s, ll, rr;
      |               ^~
teams.cpp:22:21: warning: declaration of 'll' shadows a member of 'PerSeg::node' [-Wshadow]
   22 |   node(node* c, int ll, int rr) {
      |                 ~~~~^~
teams.cpp:32:11: note: shadowed declaration is here
   32 |    int s, ll, rr;
      |           ^~
teams.cpp: In constructor 'PerSeg::node::node(PerSeg::node*, int, int)':
teams.cpp:22:29: warning: declaration of 'rr' shadows a member of 'PerSeg::node' [-Wshadow]
   22 |   node(node* c, int ll, int rr) {
      |                         ~~~~^~
teams.cpp:32:15: note: shadowed declaration is here
   32 |    int s, ll, rr;
      |               ^~
teams.cpp:22:21: warning: declaration of 'll' shadows a member of 'PerSeg::node' [-Wshadow]
   22 |   node(node* c, int ll, int rr) {
      |                 ~~~~^~
teams.cpp:32:11: note: shadowed declaration is here
   32 |    int s, ll, rr;
      |           ^~
teams.cpp: In function 'void RMQ::init(int, std::vector<int>)':
teams.cpp:119:56: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  119 |     st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
      |                                                      ~~^~~
teams.cpp: In function 'std::ostream& operator<<(std::ostream&, const segment&)':
teams.cpp:134:59: warning: declaration of 'a' shadows a global declaration [-Wshadow]
  134 |  friend ostream& operator<< (ostream& out, const segment& a) {
      |                                            ~~~~~~~~~~~~~~~^
teams.cpp:10:5: note: shadowed declaration is here
   10 | int a[N], b[N];
      |     ^
teams.cpp: In function 'bool query(int, std::vector<int>&)':
teams.cpp:140:6: warning: unused variable 'idx' [-Wunused-variable]
  140 |  int idx = 0;
      |      ^~~
teams.cpp:145:6: warning: unused variable 'ccnt' [-Wunused-variable]
  145 |  int ccnt = 1;
      |      ^~~~
teams.cpp:139:16: warning: unused parameter 'k' [-Wunused-parameter]
  139 | bool query(int k, vector<int>& s){
      |            ~~~~^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:183:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  183 | void init(int N, int A[], int B[]) {
      |           ~~~~^
teams.cpp:8:11: note: shadowed declaration is here
    8 | const int N = 5e5 + 11;
      |           ^

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