#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second
ll min (ll x, ll y){
return ((x < y) ? x : y);
}
ll max (ll x, ll y){
return ((x > y) ? x : y);
}
struct PNode {
vi v,t;
ll qry (ll curt){
/*
cout << "queried: " << curt << "\n";
for (auto i: v) cout << i << " ";
cout << endl;
for (auto i: t) cout << i << " ";
cout << endl;
*/
auto itr = upper_bound(t.begin(),t.end(),curt);
//ll idx = distance(t.begin(),itr)-1;
ll idx = (itr-t.begin())-1;
//cout << v[idx] << endl;
return v[idx];
}
ll lst_qry(){
return v.back();
}
void inc_update (ll vn, ll tn){
if (t.back() != tn){
v.push_back(lst_qry()+vn);
t.push_back(tn);
}else{
v[v.size()-1] += vn;
}
}
void change_update (ll vn, ll tn){
if (t.back() != tn){
v.push_back(vn);
t.push_back(tn);
}else{
v[v.size()-1] = vn;
}
}
PNode (){ v = vi{0}; t = vi{0}; }
};
class SegTree {
private:
vector<PNode> st;
ll n;
ll left (ll x){ return (x << 1) ; }
ll right (ll x){ return (x << 1) + 1; }
void update (ll i, ll l, ll r, ll idx, ll inc, ll t){
// assumed that t is updated increasingly
if (r >= idx && idx >= l){
if (l == r){
st[i].inc_update(inc,t);
}else{
//cout << i << " " << l << " -> " << r << " : " << st[i].lst_qry() << endl;
ll m = (l+r)/2;
update(left(i),l,m,idx,inc,t);
update(right(i),m+1,r,idx,inc,t);
st[i].change_update(st[left(i)].lst_qry()+st[right(i)].lst_qry(),t);
}
//cout << i << " " << t << " , " << l << " -> " << r << " : " << st[i].lst_qry() << endl;
}
}
ll query (ll i, ll l, ll r, ll ql, ll qr, ll t){
//cout << i << " " << l << " " << r << " " << ql << " " << qr << endl;
if (qr >= r && l >= ql){
/*
cout << "queried: \n";
cout << "params: " << i << " " << l << " " << r << endl;
cout << "result: " << st[i].qry(t) << endl;
*/
return st[i].qry(t);
}else if (l > qr || ql > r){
return 0;
}else{
ll m = (l+r)/2;
ll lres = 0, rres = 0;
if (!(l > qr || ql > m)) lres = query(left(i),l,m,ql,qr,t);
if (!(m+1 > qr || ql > r)) rres = query(right(i),m+1,r,ql,qr,t);
return lres+rres;
}
}
public:
SegTree (){}
SegTree(ll _n): n(_n){
st.resize(4*n);
}
void update (ll idx, ll inc, ll t){
update(1,0,n-1,idx,inc,t);
}
ll query (ll ql, ll qr, ll t){
return query(1,0,n-1,ql,qr,t);
}
};
SegTree st;
ll n;
vi ctr,vals,byBucket;
void init(int _n, int a[], int b[]) {
n = _n;
st = SegTree(n+1);
vii itvls;
for (ll i = 0; n > i; i++) itvls.emplace_back(a[i],b[i]);
sort(itvls.begin(),itvls.end());
for (auto i: itvls){
//cout << i.F << " " << i.S << endl;
st.update(i.S,1,i.F);
}
ctr.assign(n,0);
vals.assign(n,0);
byBucket.assign(n,0);
}
int can(int m, int k[]) {
sort(k,k+m);
ll sum = 0;
for (ll i = 0; m > i; i++) sum += k[i];
if (sum > n) return 0;
ctr[0] = k[0];
ll ptr = 0;
for (ll i = 1; m > i; i++){
if (k[i] != k[i-1]) ctr[++ptr] = 0;
ctr[ptr] += k[i];
}
vals[0] = k[0];
ptr = 0;
for (ll i = 1; m > i; i++){
if (k[i] != k[i-1]) vals[++ptr] = k[i];
}
vals[ptr+1] = n+1;
for (ll i = 0; ptr >= i; i++) byBucket[i] = 0;
/*
cout << itr->F << " " << itr->S << endl;
cout << "vals:\n";
for (auto i: vals) cout << i << " ";
cout << endl;
*/
for (ll i = 0; ptr >= i; i++){
for (ll j = i; ptr >= j; j++){
//cout << "i: " << i << " j: " << j << endl;
if (ctr[i] == 0) break;
ll rmv = st.query(vals[j],vals[j+1]-1,vals[i])-byBucket[j];
//cout << vals[j] << " " << vals[j+1] << " " << vals[i] << ": " << rmv << endl;
//cout << "itr: " << itr->F << " " << itr->S << endl;
rmv = min(rmv,ctr[i]);
ctr[i] -= rmv;
byBucket[j] += rmv;
}
if (ctr[i] > 0) return 0;
/*
cout << itr->F << " " << itr->S << endl;
for (auto i: byBucket) cout << i << " ";
cout << endl;
*/
}
//cout << "1\n";
return 1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 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 |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 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 |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
268 ms |
83072 KB |
Output is correct |
2 |
Correct |
315 ms |
83120 KB |
Output is correct |
3 |
Correct |
320 ms |
83104 KB |
Output is correct |
4 |
Correct |
270 ms |
83144 KB |
Output is correct |
5 |
Correct |
81 ms |
49088 KB |
Output is correct |
6 |
Correct |
90 ms |
49028 KB |
Output is correct |
7 |
Correct |
73 ms |
49036 KB |
Output is correct |
8 |
Correct |
74 ms |
49068 KB |
Output is correct |
9 |
Correct |
73 ms |
48904 KB |
Output is correct |
10 |
Correct |
77 ms |
48904 KB |
Output is correct |
11 |
Correct |
97 ms |
48824 KB |
Output is correct |
12 |
Correct |
79 ms |
49092 KB |
Output is correct |
13 |
Correct |
87 ms |
53856 KB |
Output is correct |
14 |
Correct |
117 ms |
58760 KB |
Output is correct |
15 |
Correct |
250 ms |
76860 KB |
Output is correct |
16 |
Correct |
232 ms |
76624 KB |
Output is correct |
17 |
Correct |
82 ms |
49468 KB |
Output is correct |
18 |
Correct |
88 ms |
49516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
312 ms |
83004 KB |
Output is correct |
2 |
Correct |
320 ms |
83004 KB |
Output is correct |
3 |
Correct |
444 ms |
83156 KB |
Output is correct |
4 |
Correct |
275 ms |
82936 KB |
Output is correct |
5 |
Correct |
94 ms |
48912 KB |
Output is correct |
6 |
Correct |
102 ms |
48956 KB |
Output is correct |
7 |
Correct |
88 ms |
48948 KB |
Output is correct |
8 |
Correct |
97 ms |
48936 KB |
Output is correct |
9 |
Correct |
77 ms |
48760 KB |
Output is correct |
10 |
Correct |
82 ms |
48784 KB |
Output is correct |
11 |
Correct |
104 ms |
48784 KB |
Output is correct |
12 |
Correct |
1055 ms |
49044 KB |
Output is correct |
13 |
Correct |
415 ms |
53924 KB |
Output is correct |
14 |
Correct |
413 ms |
78048 KB |
Output is correct |
15 |
Correct |
297 ms |
76820 KB |
Output is correct |
16 |
Correct |
255 ms |
76692 KB |
Output is correct |
17 |
Correct |
104 ms |
49552 KB |
Output is correct |
18 |
Correct |
102 ms |
49500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1932 ms |
427972 KB |
Output is correct |
2 |
Correct |
1917 ms |
427980 KB |
Output is correct |
3 |
Correct |
2189 ms |
427924 KB |
Output is correct |
4 |
Correct |
1793 ms |
428072 KB |
Output is correct |
5 |
Correct |
454 ms |
243424 KB |
Output is correct |
6 |
Correct |
477 ms |
247376 KB |
Output is correct |
7 |
Correct |
433 ms |
247304 KB |
Output is correct |
8 |
Correct |
422 ms |
247464 KB |
Output is correct |
9 |
Correct |
453 ms |
247548 KB |
Output is correct |
10 |
Correct |
381 ms |
245700 KB |
Output is correct |
11 |
Correct |
1797 ms |
246244 KB |
Output is correct |
12 |
Correct |
3313 ms |
249012 KB |
Output is correct |
13 |
Correct |
1471 ms |
273820 KB |
Output is correct |
14 |
Correct |
2089 ms |
414188 KB |
Output is correct |
15 |
Correct |
1371 ms |
377944 KB |
Output is correct |
16 |
Correct |
1382 ms |
378232 KB |
Output is correct |
17 |
Correct |
533 ms |
252860 KB |
Output is correct |
18 |
Correct |
467 ms |
252760 KB |
Output is correct |