//#include <bits/stdc++.h>
#include <iostream>
#include <set>
#include <vector>
#include <cstdio>
#include <algorithm>
#include "teams.h"
#define pii pair<int,int>
#define ft first
#define sd second
#define MP make_pair
#define PB push_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int oo = 2e9;
const int N = 500100;
const int M = 200100;
vector<pii> events, vc;
set<int> st[M], setik;
set<int>::iterator ite, net, pre;
int n, f[M];
struct seg_tree{
seg_tree *l, *r;
int sm;
seg_tree(): l(0), r(0), sm(0) {}
seg_tree(seg_tree *v): l(v -> l), r(v -> r), sm(v -> sm) {}
void build(int tl, int tr){
sm = 0;
if (tl == tr) return;
int md = (tl + tr) >> 1;
l = new seg_tree();
r = new seg_tree();
l -> build(tl, md);
r -> build(md + 1, tr);
}
void update(int tl, int tr, int ps){
sm++;
if (tl == tr) return;
int md = (tl + tr) >> 1;
if (ps <= md){
l = new seg_tree(l);
l -> update(tl, md, ps);
} else {
r = new seg_tree(r);
r -> update(md + 1, tr, ps);
}
}
int sum(int tl, int tr, int ql, int qr){
if (ql > qr) return 0;
if (ql == tl && qr == tr) return sm;
int md = (tl + tr) >> 1;
return l -> sum(tl, md, ql, min(qr, md)) + r -> sum(md + 1, tr, max(md + 1, ql), qr);
}
};
seg_tree *root[N];
void init(int N, int A[], int B[]) {
n = N;
for (int i = 0; i < n; i++)
vc.PB(MP(A[i], B[i]));
sort(all(vc));
root[n] = new seg_tree();
root[n] -> build(1, n);
for (int i = n - 1; i >= 0; i--){
root[i] = new seg_tree(root[i + 1]);
root[i] -> update(1, n, vc[i].sd);
}
}
int calc(int x1, int y1, int x2, int y2){
int lf = lower_bound(all(vc), MP(x1, -oo)) - vc.begin();
int rt = upper_bound(all(vc), MP(x2, +oo)) - vc.begin();
return (root[lf] -> sum(1, n, y1, y2)) - (root[rt] -> sum(1, n, y1, y2));
}
bool better(int i, int j, int k){
int cr = events[k].ft;
return (f[i] + calc(events[i].ft + 1, cr, cr, n) <= f[j] + calc(events[j].ft + 1, cr, cr, n));
}
void change(int i, int j, int beg, bool insrt){
int l = beg, r = sz(events);
while (l < r){
int k = (l + r) >> 1;
if (better(i, j, k))
r = k;
else l = k + 1;
}
if (l < sz(events)) {
if (insrt)
st[l].insert(i);
else st[l].erase(i);
}
}
int can(int M, int K[]) {
sort(K, K + M);
events.clear();
ll sum = 0ll;
for (int i = 0; i < M; ){
int j = i;
events.PB(MP(K[i], 0));
while (j < M && K[i] == K[j]){
sum += K[j];
events.back().sd++;
j++;
}
i = j;
}
if (sum > ll(n)) return 0;
setik.clear();
for (int it = 0; it < sz(events); it++)
st[it].clear();
for (int it = 0; it < sz(events); it++){
pii cr = events[it];
int cur_kol = cr.ft * cr.sd;
f[it] = calc(1, cr.ft, cr.ft, n) - cur_kol;
while (sz(st[it]) > 0){
int vl = (*(--st[it].end()));
st[it].erase(--st[it].end());
ite = setik.find(vl);
int mem_net = *next(ite);
setik.erase(next(ite));
net = next(ite);
if (net != setik.end()) {
change(mem_net, *net, it, 0);
change(vl, *net, it, 1);
}
}
if (sz(setik)) {
int pr = (*(--setik.end()));
f[it] = min(f[it], f[pr] + calc(events[pr].ft + 1, cr.ft, cr.ft, n) - cur_kol);
}
if (f[it] < 0)
return 0;
if (!sz(setik)){
setik.insert(it);
continue;
}
int lst = (*(--setik.end()));
if (it + 1 < sz(events) && !better(lst, it, it + 1)){
change(lst, it, it + 1, 1);
setik.insert(it);
}
}
return 1;
}
Compilation message
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:75:34: warning: declaration of 'N' shadows a global declaration [-Wshadow]
void init(int N, int A[], int B[]) {
^
teams.cpp:18:11: note: shadowed declaration is here
const int N = 500100;
^
teams.cpp: In function 'int calc(int, int, int, int)':
teams.cpp:93:48: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
int lf = lower_bound(all(vc), MP(x1, -oo)) - vc.begin();
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
teams.cpp:94:48: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
int rt = upper_bound(all(vc), MP(x2, +oo)) - vc.begin();
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:122:23: warning: declaration of 'M' shadows a global declaration [-Wshadow]
int can(int M, int K[]) {
^
teams.cpp:19:11: note: shadowed declaration is here
const int M = 200100;
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
9728 KB |
Output is correct |
2 |
Correct |
9 ms |
9728 KB |
Output is correct |
3 |
Correct |
10 ms |
9856 KB |
Output is correct |
4 |
Correct |
10 ms |
9728 KB |
Output is correct |
5 |
Correct |
9 ms |
9856 KB |
Output is correct |
6 |
Correct |
9 ms |
9728 KB |
Output is correct |
7 |
Correct |
10 ms |
9728 KB |
Output is correct |
8 |
Correct |
10 ms |
9728 KB |
Output is correct |
9 |
Correct |
10 ms |
9856 KB |
Output is correct |
10 |
Correct |
10 ms |
9728 KB |
Output is correct |
11 |
Correct |
10 ms |
9728 KB |
Output is correct |
12 |
Correct |
10 ms |
9728 KB |
Output is correct |
13 |
Correct |
10 ms |
9856 KB |
Output is correct |
14 |
Correct |
10 ms |
9728 KB |
Output is correct |
15 |
Correct |
9 ms |
9728 KB |
Output is correct |
16 |
Correct |
10 ms |
9728 KB |
Output is correct |
17 |
Correct |
9 ms |
9728 KB |
Output is correct |
18 |
Correct |
9 ms |
9728 KB |
Output is correct |
19 |
Correct |
10 ms |
9728 KB |
Output is correct |
20 |
Correct |
10 ms |
9728 KB |
Output is correct |
21 |
Correct |
10 ms |
9728 KB |
Output is correct |
22 |
Correct |
10 ms |
9728 KB |
Output is correct |
23 |
Correct |
10 ms |
9728 KB |
Output is correct |
24 |
Correct |
10 ms |
9728 KB |
Output is correct |
25 |
Correct |
10 ms |
9728 KB |
Output is correct |
26 |
Correct |
10 ms |
9728 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
122 ms |
73836 KB |
Output is correct |
2 |
Correct |
125 ms |
73708 KB |
Output is correct |
3 |
Correct |
128 ms |
73888 KB |
Output is correct |
4 |
Correct |
127 ms |
74220 KB |
Output is correct |
5 |
Correct |
90 ms |
73836 KB |
Output is correct |
6 |
Correct |
90 ms |
73836 KB |
Output is correct |
7 |
Correct |
94 ms |
73708 KB |
Output is correct |
8 |
Correct |
91 ms |
73732 KB |
Output is correct |
9 |
Correct |
82 ms |
71660 KB |
Output is correct |
10 |
Correct |
84 ms |
71660 KB |
Output is correct |
11 |
Correct |
85 ms |
74732 KB |
Output is correct |
12 |
Correct |
87 ms |
71532 KB |
Output is correct |
13 |
Correct |
102 ms |
74604 KB |
Output is correct |
14 |
Correct |
96 ms |
72300 KB |
Output is correct |
15 |
Correct |
116 ms |
73708 KB |
Output is correct |
16 |
Correct |
120 ms |
73708 KB |
Output is correct |
17 |
Correct |
98 ms |
74604 KB |
Output is correct |
18 |
Correct |
94 ms |
74604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
136 ms |
74092 KB |
Output is correct |
2 |
Correct |
134 ms |
74092 KB |
Output is correct |
3 |
Correct |
286 ms |
77164 KB |
Output is correct |
4 |
Correct |
123 ms |
74092 KB |
Output is correct |
5 |
Correct |
226 ms |
74220 KB |
Output is correct |
6 |
Correct |
208 ms |
74196 KB |
Output is correct |
7 |
Correct |
100 ms |
74244 KB |
Output is correct |
8 |
Correct |
183 ms |
74092 KB |
Output is correct |
9 |
Correct |
82 ms |
71660 KB |
Output is correct |
10 |
Correct |
87 ms |
71960 KB |
Output is correct |
11 |
Correct |
115 ms |
75092 KB |
Output is correct |
12 |
Correct |
535 ms |
72044 KB |
Output is correct |
13 |
Correct |
519 ms |
75116 KB |
Output is correct |
14 |
Correct |
329 ms |
75372 KB |
Output is correct |
15 |
Correct |
349 ms |
74220 KB |
Output is correct |
16 |
Correct |
338 ms |
74220 KB |
Output is correct |
17 |
Correct |
258 ms |
75116 KB |
Output is correct |
18 |
Correct |
301 ms |
75116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
762 ms |
366040 KB |
Output is correct |
2 |
Correct |
765 ms |
365964 KB |
Output is correct |
3 |
Correct |
1248 ms |
371932 KB |
Output is correct |
4 |
Correct |
750 ms |
366048 KB |
Output is correct |
5 |
Correct |
779 ms |
366048 KB |
Output is correct |
6 |
Correct |
741 ms |
366048 KB |
Output is correct |
7 |
Correct |
477 ms |
365920 KB |
Output is correct |
8 |
Correct |
691 ms |
365908 KB |
Output is correct |
9 |
Correct |
408 ms |
350944 KB |
Output is correct |
10 |
Correct |
438 ms |
366736 KB |
Output is correct |
11 |
Correct |
735 ms |
366844 KB |
Output is correct |
12 |
Correct |
1601 ms |
366952 KB |
Output is correct |
13 |
Correct |
1842 ms |
366688 KB |
Output is correct |
14 |
Correct |
1359 ms |
367328 KB |
Output is correct |
15 |
Correct |
1265 ms |
373708 KB |
Output is correct |
16 |
Correct |
1219 ms |
373588 KB |
Output is correct |
17 |
Correct |
989 ms |
373476 KB |
Output is correct |
18 |
Correct |
1004 ms |
373504 KB |
Output is correct |