#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 = 1;
struct NODE{
int l, r, cnt;
NODE *lp, *rp;
NODE(int a, int b, int c) : l(a), r(b), cnt(c), lp(NULL), rp(NULL) {}
NODE(int a, int b) : l(a), r(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 v) {
if(r < v || v < l) return this;
NODE *res = new NODE(l, r, cnt);
if(l != r) {
res->lp = lp->add(v);
res->rp = rp->add(v);
}
res->cnt++;
return res;
}
int getCnt(int a, int b) {
if(r < a || b < l) return 0;
if(a <= l && r <= b) return cnt;
return lp->getCnt(a, b) + rp->getCnt(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);
}
root[0] = new NODE(1, N);
for(int i=0; i<N; i++)
root[i+1] = root[i] -> add(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;
}
int getCnt(int x0, int x1, int y0, int y1) {
return root[y1] -> getCnt(x0, x1) - root[y0-1] -> getCnt(x0, x1);
}
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);
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 newX = -1;
for(int l=xi, r=px; l<=r; ) {
int m = (l+r) >> 1;
int now = getCnt(xi, m, py+1, yi);
if(now == cnt) {newX = m; break;}
if(now < cnt) l = m+1; else r = m-1;
}
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:60:33: warning: declaration of 'pi b' shadows a parameter [-Wshadow]
sort(ALL(Ps), [&](pi a, pi b) {return a.one < b.one;});
^
teams.cpp:52:33: note: shadowed declaration is here
void init(int n, int a[], int b[]) {
^
teams.cpp:60:33: warning: declaration of 'pi a' shadows a parameter [-Wshadow]
sort(ALL(Ps), [&](pi a, pi b) {return a.one < b.one;});
^
teams.cpp:52:24: note: shadowed declaration is here
void init(int n, int a[], int b[]) {
^
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.two < b.two;});
^
teams.cpp:52: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.two < b.two;});
^
teams.cpp:52: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:78: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:81: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;
^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:106:25: warning: declaration of 'int m' shadows a parameter [-Wshadow]
int m = (l+r) >> 1;
^
teams.cpp:88:13: note: shadowed declaration is here
int can(int m, int k[]) {
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
5960 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
313 ms |
101148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
319 ms |
101544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Memory limit exceeded |
1829 ms |
524288 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
