oj.uz

Submission #641809

# Submission time Handle Problem Language Result Execution time Memory
641809 2022-09-17T16:05:19 Z QwertyPi Teams (IOI15_teams) C++14
100 / 100
 1284 ms 238408 KB 
#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 176380 KB Output is correct
2 Correct 86 ms 176364 KB Output is correct
3 Correct 76 ms 176436 KB Output is correct
4 Correct 81 ms 176460 KB Output is correct
5 Correct 78 ms 176496 KB Output is correct
6 Correct 86 ms 176560 KB Output is correct
7 Correct 85 ms 176460 KB Output is correct
8 Correct 88 ms 176436 KB Output is correct
9 Correct 81 ms 176404 KB Output is correct
10 Correct 77 ms 176420 KB Output is correct
11 Correct 76 ms 176460 KB Output is correct
12 Correct 87 ms 176460 KB Output is correct
13 Correct 76 ms 176460 KB Output is correct
14 Correct 77 ms 176476 KB Output is correct
15 Correct 77 ms 176588 KB Output is correct
16 Correct 81 ms 176476 KB Output is correct
17 Correct 77 ms 176448 KB Output is correct
18 Correct 78 ms 176444 KB Output is correct
19 Correct 79 ms 176416 KB Output is correct
20 Correct 76 ms 176420 KB Output is correct
21 Correct 76 ms 176412 KB Output is correct
22 Correct 77 ms 176428 KB Output is correct
23 Correct 79 ms 176460 KB Output is correct
24 Correct 76 ms 176424 KB Output is correct
25 Correct 76 ms 176392 KB Output is correct
26 Correct 82 ms 176376 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 187080 KB Output is correct
2 Correct 130 ms 187032 KB Output is correct
3 Correct 123 ms 187072 KB Output is correct
4 Correct 190 ms 187664 KB Output is correct
5 Correct 110 ms 186676 KB Output is correct
6 Correct 107 ms 186688 KB Output is correct
7 Correct 106 ms 186692 KB Output is correct
8 Correct 106 ms 186688 KB Output is correct
9 Correct 127 ms 186816 KB Output is correct
10 Correct 115 ms 186440 KB Output is correct
11 Correct 102 ms 186488 KB Output is correct
12 Correct 101 ms 186620 KB Output is correct
13 Correct 109 ms 186792 KB Output is correct
14 Correct 114 ms 186924 KB Output is correct
15 Correct 121 ms 187072 KB Output is correct
16 Correct 123 ms 187072 KB Output is correct
17 Correct 107 ms 187036 KB Output is correct
18 Correct 108 ms 186916 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 187456 KB Output is correct
2 Correct 132 ms 187232 KB Output is correct
3 Correct 350 ms 190260 KB Output is correct
4 Correct 129 ms 187704 KB Output is correct
5 Correct 146 ms 186896 KB Output is correct
6 Correct 140 ms 186948 KB Output is correct
7 Correct 111 ms 186956 KB Output is correct
8 Correct 133 ms 187096 KB Output is correct
9 Correct 135 ms 186732 KB Output is correct
10 Correct 178 ms 186588 KB Output is correct
11 Correct 192 ms 186624 KB Output is correct
12 Correct 204 ms 186816 KB Output is correct
13 Correct 269 ms 186980 KB Output is correct
14 Correct 426 ms 188728 KB Output is correct
15 Correct 208 ms 187140 KB Output is correct
16 Correct 204 ms 187196 KB Output is correct
17 Correct 184 ms 187108 KB Output is correct
18 Correct 189 ms 187152 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 234168 KB Output is correct
2 Correct 450 ms 234064 KB Output is correct
3 Correct 1132 ms 238408 KB Output is correct
4 Correct 467 ms 234056 KB Output is correct
5 Correct 330 ms 231412 KB Output is correct
6 Correct 310 ms 231332 KB Output is correct
7 Correct 240 ms 231420 KB Output is correct
8 Correct 306 ms 231400 KB Output is correct
9 Correct 369 ms 231860 KB Output is correct
10 Correct 386 ms 229964 KB Output is correct
11 Correct 437 ms 230524 KB Output is correct
12 Correct 445 ms 230960 KB Output is correct
13 Correct 782 ms 232532 KB Output is correct
14 Correct 1284 ms 235012 KB Output is correct
15 Correct 558 ms 233876 KB Output is correct
16 Correct 560 ms 233968 KB Output is correct
17 Correct 402 ms 233284 KB Output is correct
18 Correct 410 ms 233412 KB Output is correct