# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
31000 |
2017-08-03T08:15:21 Z |
kajebiii |
Teams (IOI15_teams) |
C++14 |
|
3106 ms |
367292 KB |
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<double, double> pd;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;
const int MAX_N = 5e5 + 100, DEBUG = 0;
struct NODE{
int cnt;
NODE *lp, *rp;
NODE(int c) : cnt(c), lp(NULL), rp(NULL) {}
NODE(int a, int b) : cnt(0), lp(NULL), rp(NULL) {
if(a == b) return;
int m = (a+b) >> 1;
lp = new NODE(a, m);
rp = new NODE(m+1, b);
}
NODE *add(int l, int r, int v) {
if(r < v || v < l) return this;
NODE *res = new NODE(cnt);
int m = (l+r) >> 1;
if(l != r) {
res->lp = lp->add(l, m, v);
res->rp = rp->add(m+1, r, v);
}
res->cnt++;
return res;
}
int getCnt(int l, int r, int a, int b) {
if(r < a || b < l) return 0;
if(a <= l && r <= b) return cnt;
int m = (l+r) >> 1;
return lp->getCnt(l, m, a, b) + rp->getCnt(m+1, r, a, b);
}
};
NODE *root[MAX_N];
int N, *A, *B; vector<pi> Ps;
vector<int> CoX, CoY;
void init(int n, int a[], int b[]) {
N = n; A = a; B = b;
for(int i=0; i<N; i++) {
CoX.push_back(B[i]);
CoY.push_back(A[i]);
Ps.push_back(pi(B[i], A[i]));
}
sort(ALL(CoX)); sort(ALL(CoY));
sort(ALL(Ps), [&](pi a, pi b) {return a.one < b.one;});
for(int i=0; i<N; i++) Ps[i].one = i+1;
sort(ALL(Ps), [&](pi a, pi b) {return a.two < b.two;});
for(int i=0; i<N; i++) Ps[i].two = i+1;
if(DEBUG) {
printf("Y : "); for(int i=0; i<N; i++) printf("%d ", CoY[i]); puts("");
printf("X : "); for(int i=0; i<N; i++) printf("%d ", CoX[i]); puts("");
for(int i=0; i<N; i++) printf("[%d %d] ", Ps[i].one, Ps[i].two); puts("");
}
root[0] = new NODE(1, N);
for(int i=0; i<N; i++)
root[i+1] = root[i] -> add(1, N, Ps[i].one);
}
int getUix(int k, vector<int> &v) {
return (upper_bound(ALL(v), k) - v.begin() - 1) + 1;
}
int getLix(int k, vector<int> &v) {
return (lower_bound(ALL(v), k) - v.begin()) + 1;
}
bool isBetween(int k, int x, int y) {
return x <= k && k <= y;
}
int getCnt(int x0, int x1, int y0, int y1) {
// int cnt = 0;for(int i=0; i<N; i++) if(isBetween(Ps[i].one, x0, x1) & isBetween(Ps[i].two, y0, y1)) cnt++;
// printf("[%d %d %d %d] => %d\n", x0, x1, y0, y1, cnt);
// return cnt;
return root[y1] -> getCnt(1, N, x0, x1) - root[y0-1] -> getCnt(1, N, x0, x1);
}
int findX(NODE *mp, NODE *pp, int l, int r, int v) {
if(l == r) return l;
int m = (l+r) >> 1;
int lcnt = pp->lp->cnt - mp->lp->cnt;
if(lcnt >= v) return findX(mp->lp, pp->lp, l, m, v);
return findX(mp->rp, pp->rp, m+1, r, v-lcnt);
}
int M, *K;
int can(int m, int k[]) {
M = m; K = k;
sort(K, K+M);
stack<pi> S; S.push(pi(0, MAX_N)); // (y, x);
for(int mi=0; mi<M; mi++) {
int v = K[mi];
int yi = getUix(v, CoY);
int xi = getLix(v, CoX);
// printf("yi : %d | xi : %d\n", yi, xi);
while(true) {
while(S.top().two < xi) S.pop();
int py, px; tie(py, px) = S.top();
int cnt = getCnt(xi, px, py+1, yi);
if(cnt >= v) {
int base = getCnt(1, xi-1, py+1, yi);
int newX = findX(root[py], root[yi], 1, N, v+base);
S.push(pi(yi, newX));
break;
}else{
v -= cnt;
xi = px+1;
S.pop();
if(S.size() == 0) {
return 0;
}
}
}
}
return 1;
}
Compilation message
teams.cpp: In lambda function:
teams.cpp:62:33: warning: declaration of 'pi b' shadows a parameter [-Wshadow]
sort(ALL(Ps), [&](pi a, pi b) {return a.one < b.one;});
^
teams.cpp:54:33: note: shadowed declaration is here
void init(int n, int a[], int b[]) {
^
teams.cpp:62:33: warning: declaration of 'pi a' shadows a parameter [-Wshadow]
sort(ALL(Ps), [&](pi a, pi b) {return a.one < b.one;});
^
teams.cpp:54:24: note: shadowed declaration is here
void init(int n, int a[], int b[]) {
^
teams.cpp: In lambda function:
teams.cpp:64:33: warning: declaration of 'pi b' shadows a parameter [-Wshadow]
sort(ALL(Ps), [&](pi a, pi b) {return a.two < b.two;});
^
teams.cpp:54:33: note: shadowed declaration is here
void init(int n, int a[], int b[]) {
^
teams.cpp:64:33: warning: declaration of 'pi a' shadows a parameter [-Wshadow]
sort(ALL(Ps), [&](pi a, pi b) {return a.two < b.two;});
^
teams.cpp:54:24: note: shadowed declaration is here
void init(int n, int a[], int b[]) {
^
teams.cpp: In function 'int getUix(int, std::vector<int>&)':
teams.cpp:80:55: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
return (upper_bound(ALL(v), k) - v.begin() - 1) + 1;
^
teams.cpp: In function 'int getLix(int, std::vector<int>&)':
teams.cpp:83:51: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
return (lower_bound(ALL(v), k) - v.begin()) + 1;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
5960 KB |
Output is correct |
2 |
Correct |
0 ms |
5960 KB |
Output is correct |
3 |
Correct |
0 ms |
5960 KB |
Output is correct |
4 |
Correct |
0 ms |
5960 KB |
Output is correct |
5 |
Correct |
0 ms |
5960 KB |
Output is correct |
6 |
Correct |
0 ms |
6108 KB |
Output is correct |
7 |
Correct |
0 ms |
5960 KB |
Output is correct |
8 |
Correct |
0 ms |
5960 KB |
Output is correct |
9 |
Correct |
0 ms |
5960 KB |
Output is correct |
10 |
Correct |
0 ms |
5960 KB |
Output is correct |
11 |
Correct |
0 ms |
5960 KB |
Output is correct |
12 |
Correct |
0 ms |
5960 KB |
Output is correct |
13 |
Correct |
0 ms |
5960 KB |
Output is correct |
14 |
Correct |
0 ms |
5960 KB |
Output is correct |
15 |
Correct |
0 ms |
5960 KB |
Output is correct |
16 |
Correct |
0 ms |
5960 KB |
Output is correct |
17 |
Correct |
0 ms |
5960 KB |
Output is correct |
18 |
Correct |
0 ms |
5960 KB |
Output is correct |
19 |
Correct |
0 ms |
5960 KB |
Output is correct |
20 |
Correct |
0 ms |
5960 KB |
Output is correct |
21 |
Correct |
0 ms |
5960 KB |
Output is correct |
22 |
Correct |
0 ms |
5960 KB |
Output is correct |
23 |
Correct |
0 ms |
5960 KB |
Output is correct |
24 |
Correct |
0 ms |
5960 KB |
Output is correct |
25 |
Correct |
0 ms |
5960 KB |
Output is correct |
26 |
Correct |
0 ms |
5960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
213 ms |
70392 KB |
Output is correct |
2 |
Correct |
189 ms |
70392 KB |
Output is correct |
3 |
Correct |
189 ms |
70392 KB |
Output is correct |
4 |
Correct |
169 ms |
70800 KB |
Output is correct |
5 |
Correct |
109 ms |
70392 KB |
Output is correct |
6 |
Correct |
113 ms |
70392 KB |
Output is correct |
7 |
Correct |
133 ms |
70392 KB |
Output is correct |
8 |
Correct |
103 ms |
70392 KB |
Output is correct |
9 |
Correct |
133 ms |
70536 KB |
Output is correct |
10 |
Correct |
109 ms |
70392 KB |
Output is correct |
11 |
Correct |
89 ms |
70392 KB |
Output is correct |
12 |
Correct |
99 ms |
70392 KB |
Output is correct |
13 |
Correct |
169 ms |
70392 KB |
Output is correct |
14 |
Correct |
129 ms |
70392 KB |
Output is correct |
15 |
Correct |
139 ms |
70392 KB |
Output is correct |
16 |
Correct |
193 ms |
70392 KB |
Output is correct |
17 |
Correct |
113 ms |
70392 KB |
Output is correct |
18 |
Correct |
143 ms |
70392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
226 ms |
70788 KB |
Output is correct |
2 |
Correct |
233 ms |
70788 KB |
Output is correct |
3 |
Correct |
746 ms |
73428 KB |
Output is correct |
4 |
Correct |
176 ms |
70800 KB |
Output is correct |
5 |
Correct |
299 ms |
70788 KB |
Output is correct |
6 |
Correct |
339 ms |
70788 KB |
Output is correct |
7 |
Correct |
116 ms |
70788 KB |
Output is correct |
8 |
Correct |
246 ms |
70788 KB |
Output is correct |
9 |
Correct |
159 ms |
70536 KB |
Output is correct |
10 |
Correct |
226 ms |
70696 KB |
Output is correct |
11 |
Correct |
299 ms |
70792 KB |
Output is correct |
12 |
Correct |
306 ms |
70788 KB |
Output is correct |
13 |
Correct |
513 ms |
70788 KB |
Output is correct |
14 |
Correct |
783 ms |
72108 KB |
Output is correct |
15 |
Correct |
279 ms |
70788 KB |
Output is correct |
16 |
Correct |
263 ms |
70788 KB |
Output is correct |
17 |
Correct |
226 ms |
70788 KB |
Output is correct |
18 |
Correct |
239 ms |
70788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1329 ms |
361880 KB |
Output is correct |
2 |
Correct |
1306 ms |
361880 KB |
Output is correct |
3 |
Correct |
2606 ms |
367292 KB |
Output is correct |
4 |
Correct |
1106 ms |
361924 KB |
Output is correct |
5 |
Correct |
1599 ms |
361880 KB |
Output is correct |
6 |
Correct |
1369 ms |
361880 KB |
Output is correct |
7 |
Correct |
569 ms |
361880 KB |
Output is correct |
8 |
Correct |
1326 ms |
361880 KB |
Output is correct |
9 |
Correct |
719 ms |
361796 KB |
Output is correct |
10 |
Correct |
859 ms |
361836 KB |
Output is correct |
11 |
Correct |
1216 ms |
361880 KB |
Output is correct |
12 |
Correct |
1666 ms |
361880 KB |
Output is correct |
13 |
Correct |
2366 ms |
362012 KB |
Output is correct |
14 |
Correct |
3106 ms |
364652 KB |
Output is correct |
15 |
Correct |
1336 ms |
362012 KB |
Output is correct |
16 |
Correct |
1269 ms |
362012 KB |
Output is correct |
17 |
Correct |
899 ms |
361880 KB |
Output is correct |
18 |
Correct |
1039 ms |
361880 KB |
Output is correct |