# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
559824 |
2022-05-10T17:13:24 Z |
emuyumi |
Teams (IOI15_teams) |
C++17 |
|
3566 ms |
175740 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Segtree{
#define mid ((l + r) >> 1)
struct Node{
int lc, rc, val;
};
int N;
vector<Node> st;
int T;
Segtree() = default;
Segtree(int N) : N(N) {
st.resize(25 * N);
T = 0;
build(0, 1, N);
}
int build(int v, int l, int r){
if (l == r) return v;
st[v].lc = build(++T, l, mid);
st[v].rc = build(++T, mid + 1, r);
return v;
}
int insert(int v, int l, int r, int idx){
int nv = ++T;
if (l == r){
st[nv] = {0, 0, st[v].val + 1};
}
else if (idx <= mid){
st[nv].lc = insert(st[v].lc, l, mid, idx);
st[nv].rc = st[v].rc;
st[nv].val = st[st[nv].lc].val + st[st[nv].rc].val;
}
else{
st[nv].lc = st[v].lc;
st[nv].rc = insert(st[v].rc, mid + 1, r, idx);
st[nv].val = st[st[nv].lc].val + st[st[nv].rc].val;
}
return nv;
}
int insert(int v, int idx){ return insert(v, 1, N, idx); }
int query(int vl, int vr, int l, int r, int ql, int qr){
if (l > qr || r < ql || ql > qr) return 0;
if (l >= ql && r <= qr) return st[vr].val - st[vl].val;
return query(st[vl].lc, st[vr].lc, l, mid, ql, qr) +
query(st[vl].rc, st[vr].rc, mid + 1, r, ql, qr);
}
int query(int vl, int vr, int ql, int qr){ return query(vl, vr, 1, N, ql, qr); }
#undef mid
};
using pii = pair<int, int>;
Segtree st;
vector<int> rts;
int N;
vector<pii> xs, ys;
void init(int N, int A[], int B[]){
::N = N;
for (int i = 0; i < N; ++i){
xs.push_back({A[i], i});
ys.push_back({B[i], i});
}
// give each point unique x and unique y
sort(xs.begin(), xs.end());
sort(ys.begin(), ys.end());
vector<int> y(N + 1);
for (int i = 0; i < N; ++i){
int x = lower_bound(xs.begin(), xs.end(), pii{A[i], i}) - xs.begin() + 1;
y[x] = lower_bound(ys.begin(), ys.end(), pii{B[i], i}) - ys.begin() + 1;
// cerr << x << " " << y[x] << '\n';
}
st = Segtree(N + 1);
rts.resize(N + 1);
int v = 0;
for (int x = 1; x <= N; ++x){
v = st.insert(v, y[x]);
rts[x] = v;
}
}
// number of points in [x1, x2] x [y1, y2]
int count(int x1, int x2, int y1, int y2){
x2 = min(x2, N);
y2 = min(y2, N);
return st.query(rts[x1 - 1], rts[x2], y1, y2);
}
int can(int M, int K[]){
sort(K, K + M);
struct Point{ int x, y; };
vector<Point> stk = {};
stk.push_back({0, N + 1});
for (int i = 0; i < M; ++i){
int qx = upper_bound(xs.begin(), xs.end(), pii{K[i], 1e9}) - xs.begin() + 1 - 1;
int qy = lower_bound(ys.begin(), ys.end(), pii{K[i], -1}) - ys.begin() + 1;
while (stk.back().y < qy){
stk.pop_back();
}
int need = K[i];
while (need){
if (stk.empty()){
return 0;
}
auto [lx, ly] = stk.back();
/*
**........^
**........^
*****%%%%%% ly
*****%%%%%% qy
***********
***********
lx qx
*/
int rect = count(lx + 1, qx, qy, ly);
// cerr << lx + 1 << " " << qx << " " << qy << " " << ly << '\n';
// cerr << rect << '\n';
if (rect <= need){
need -= rect;
qy = ly + 1;
stk.pop_back();
}
else{
// bsearch for new y
int lo = qy - 1, hi = ly;
while (lo < hi){
int mi = (lo + hi) >> 1;
int cnt = count(lx + 1, qx, qy, mi);
if (cnt >= need) hi = mi;
else lo = mi + 1;
}
need = 0;
qy = lo + 1;
}
}
stk.push_back({qx, qy - 1});
}
return 1;
}
Compilation message
teams.cpp: In constructor 'Segtree::Segtree(int)':
teams.cpp:19:17: warning: declaration of 'N' shadows a member of 'Segtree' [-Wshadow]
19 | Segtree(int N) : N(N) {
| ~~~~^
teams.cpp:14:9: note: shadowed declaration is here
14 | int N;
| ^
teams.cpp: In constructor 'Segtree::Segtree(int)':
teams.cpp:19:17: warning: declaration of 'N' shadows a member of 'Segtree' [-Wshadow]
19 | Segtree(int N) : N(N) {
| ~~~~^
teams.cpp:14:9: note: shadowed declaration is here
14 | int N;
| ^
teams.cpp: In constructor 'Segtree::Segtree(int)':
teams.cpp:19:17: warning: declaration of 'N' shadows a member of 'Segtree' [-Wshadow]
19 | Segtree(int N) : N(N) {
| ~~~~^
teams.cpp:14:9: note: shadowed declaration is here
14 | int N;
| ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:70:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
70 | void init(int N, int A[], int B[]){
| ~~~~^
teams.cpp:67:5: note: shadowed declaration is here
67 | int N;
| ^
teams.cpp:84:78: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
84 | int x = lower_bound(xs.begin(), xs.end(), pii{A[i], i}) - xs.begin() + 1;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:85:77: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
85 | y[x] = lower_bound(ys.begin(), ys.end(), pii{B[i], i}) - ys.begin() + 1;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:114:85: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
114 | int qx = upper_bound(xs.begin(), xs.end(), pii{K[i], 1e9}) - xs.begin() + 1 - 1;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:115:80: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
115 | int qy = lower_bound(ys.begin(), ys.end(), pii{K[i], -1}) - ys.begin() + 1;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
3 ms |
340 KB |
Output is correct |
13 |
Correct |
2 ms |
340 KB |
Output is correct |
14 |
Correct |
2 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
292 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
316 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
300 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
108 ms |
33892 KB |
Output is correct |
2 |
Correct |
105 ms |
33996 KB |
Output is correct |
3 |
Correct |
102 ms |
33848 KB |
Output is correct |
4 |
Correct |
102 ms |
34216 KB |
Output is correct |
5 |
Correct |
77 ms |
33560 KB |
Output is correct |
6 |
Correct |
88 ms |
33512 KB |
Output is correct |
7 |
Correct |
76 ms |
33472 KB |
Output is correct |
8 |
Correct |
87 ms |
33524 KB |
Output is correct |
9 |
Correct |
180 ms |
33720 KB |
Output is correct |
10 |
Correct |
121 ms |
33228 KB |
Output is correct |
11 |
Correct |
70 ms |
33308 KB |
Output is correct |
12 |
Correct |
61 ms |
33404 KB |
Output is correct |
13 |
Correct |
92 ms |
33692 KB |
Output is correct |
14 |
Correct |
84 ms |
33672 KB |
Output is correct |
15 |
Correct |
87 ms |
33864 KB |
Output is correct |
16 |
Correct |
93 ms |
33816 KB |
Output is correct |
17 |
Correct |
75 ms |
33880 KB |
Output is correct |
18 |
Correct |
74 ms |
33868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
110 ms |
34392 KB |
Output is correct |
2 |
Correct |
103 ms |
34232 KB |
Output is correct |
3 |
Correct |
635 ms |
37608 KB |
Output is correct |
4 |
Correct |
97 ms |
34016 KB |
Output is correct |
5 |
Correct |
134 ms |
33872 KB |
Output is correct |
6 |
Correct |
130 ms |
33840 KB |
Output is correct |
7 |
Correct |
83 ms |
33868 KB |
Output is correct |
8 |
Correct |
129 ms |
33928 KB |
Output is correct |
9 |
Correct |
166 ms |
33640 KB |
Output is correct |
10 |
Correct |
509 ms |
33484 KB |
Output is correct |
11 |
Correct |
616 ms |
33664 KB |
Output is correct |
12 |
Correct |
741 ms |
33876 KB |
Output is correct |
13 |
Correct |
1010 ms |
34312 KB |
Output is correct |
14 |
Correct |
889 ms |
36116 KB |
Output is correct |
15 |
Correct |
324 ms |
34348 KB |
Output is correct |
16 |
Correct |
407 ms |
34360 KB |
Output is correct |
17 |
Correct |
277 ms |
34276 KB |
Output is correct |
18 |
Correct |
365 ms |
34268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
723 ms |
170032 KB |
Output is correct |
2 |
Correct |
730 ms |
170148 KB |
Output is correct |
3 |
Correct |
2462 ms |
175740 KB |
Output is correct |
4 |
Correct |
722 ms |
169648 KB |
Output is correct |
5 |
Correct |
616 ms |
167340 KB |
Output is correct |
6 |
Correct |
618 ms |
167400 KB |
Output is correct |
7 |
Correct |
455 ms |
167408 KB |
Output is correct |
8 |
Correct |
555 ms |
167444 KB |
Output is correct |
9 |
Correct |
1018 ms |
167600 KB |
Output is correct |
10 |
Correct |
1490 ms |
165668 KB |
Output is correct |
11 |
Correct |
2023 ms |
166424 KB |
Output is correct |
12 |
Correct |
2598 ms |
167340 KB |
Output is correct |
13 |
Correct |
3566 ms |
168892 KB |
Output is correct |
14 |
Correct |
3068 ms |
172520 KB |
Output is correct |
15 |
Correct |
1230 ms |
170040 KB |
Output is correct |
16 |
Correct |
1236 ms |
169908 KB |
Output is correct |
17 |
Correct |
1046 ms |
169260 KB |
Output is correct |
18 |
Correct |
1053 ms |
169396 KB |
Output is correct |