# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
990291 |
2024-05-30T06:12:59 Z |
VinhLuu |
Teams (IOI15_teams) |
C++17 |
|
1758 ms |
166164 KB |
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 5e5 + 5;
int block = 555;
const int mod = 1e9 + 7;
//const ll oo = 5e18;
int n, cnt, R[N], m;
struct NODE{
int l, r, w;
} st[N * 25];
int Newchild(int val){
cnt++;
st[cnt].w = val;
st[cnt].l = st[cnt].r = 0;
return cnt;
}
int Newnode(int l,int r){
cnt++;
st[cnt].l = l, st[cnt].r = r;
st[cnt].w = st[l].w + st[r].w;
return cnt;
}
int build(int l,int r){
if(l == r) return Newchild(0);
int mid = (l + r) / 2;
return Newnode(build(l, mid), build(mid + 1, r));
}
int update(int i,int l,int r,int u){
if(l > u || r < u) return i;
if(l == r) return Newchild(st[i].w + 1);
int mid = (l + r) / 2;
return Newnode(update(st[i].l, l, mid, u), update(st[i].r, mid + 1, r, u));
}
int get(int i,int l,int r,int u,int v){
if(l > r || l > v || r < u) return 0;
if(u <= l && r <= v) return st[i].w;
int mid = (l + r) / 2;
return get(st[i].l, l, mid, u, v) + get(st[i].r, mid + 1, r, u, v);
}
vector<int> add[N];
int sign[N];
void init(int _n, int A[], int B[]){
n = _n;
m = 0;
vector<int> vr;
for(int i = 0; i < n; i ++) vr.pb(i);
sort(all(vr), [&] (int x,int y){return (B[x] == B[y] ? A[x] < A[y] : B[x] < B[y]);});
int ptr = 0;
for(int i = 1; i <= n + 1; i ++) sign[i] = n + 1;
for(int i = n - 1; i >= 0; i --){
// cerr << B[vr[i]] << " ";
sign[B[vr[i]]] = i + 1;
B[vr[i]] = i + 1;
}
// cerr << "\n";
for(int i = n; i >= 1; i --){
sign[i] = min(sign[i + 1], sign[i]);
}
for(int i = 0; i < n; i ++){
add[A[i]].pb(B[i]);
}
R[0] = build(1, n);
for(int i = 1; i <= n; i ++){
int cur = R[i - 1], tmp = 0;
for(auto j : add[i]){
tmp = update(cur, 1, n, j);
swap(tmp, cur);
}
R[i] = cur;
}
}
ll mark[N], sub;
vector<int> K;
vector<pii> sk;
ll cal(int i,int mid){
if(mid == 0) return 0;
ll val = get(R[K[i]], 1, n, 1, mid);
if(sk.empty()) val -= sub;
else if(sk[0].fi <= mid) val -= sub;
else{
int le = 0, ri = sk.size() - 1, mi, u = -1;
while(le <= ri){mi = (le + ri) / 2;
if(sk[mi].fi >= mid) u = mi, le = mi + 1; else ri = mi - 1;}
int lef = (u == sk.size() - 1 ? 1 : sk[u + 1].fi + 1);
val = val - (sub - mark[sk[u].se] + get(R[K[sk[u].se]], 1, n, lef, mid));
}
return val;
}
int can(int M,int k[]){
K.clear(), sk.clear();
int sum = 0;
for(int i = 0; i < M; i ++){
mark[i] = 0, K.pb(k[i]);
sum += k[i];
}
sort(all(K));
if(K.back() > n || sum > n) return 0;
sub = 0;
for(int i = 0; i < M; i ++){
int l = sign[K[i]], r = n, mid, ans = -1;
ll w = cal(i, sign[K[i]] - 1);
while(l <= r){
mid = (l + r) / 2;
ll val = cal(i, mid) - w;
if(val >= K[i]){
ans = mid;
r = mid - 1;
}else l = mid + 1;
}
if(ans == -1) return 0;
int tmp = 1; bool gg = 0;
while(!sk.empty() && sk.back().fi <= ans){
sub = sub - get(R[K[sk.back().se]], 1, n, tmp, sk.back().fi);
tmp = sk.back().fi + 1;
gg = 1;
sk.pop_back();
}
if(!sk.empty() && gg){
mark[sk.back().se] += get(R[K[sk.back().se]], 1, n, 1, tmp - 1);
sub += get(R[K[sk.back().se]], 1, n, 1, tmp - 1);
}
if(!sk.empty()){
int lmao = get(R[K[sk.back().se]], 1, n, 1, ans);
mark[sk.back().se] -= lmao;
sub -= lmao;
}
mark[i] = get(R[K[i]], 1, n, 1, ans) + (sk.empty() ? 0 : mark[sk.back().se]);
sub += get(R[K[i]], 1, n, 1, ans);
sk.pb({ans, i});
}
return 1;
}
Compilation message
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:66:8: warning: unused variable 'ptr' [-Wunused-variable]
66 | int ptr = 0;
| ^~~
teams.cpp: In function 'long long int cal(int, int)':
teams.cpp:103:34: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
103 | int le = 0, ri = sk.size() - 1, mi, u = -1;
| ~~~~~~~~~~^~~
teams.cpp:107:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | int lef = (u == sk.size() - 1 ? 1 : sk[u + 1].fi + 1);
| ~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
16732 KB |
Output is correct |
2 |
Correct |
2 ms |
16732 KB |
Output is correct |
3 |
Correct |
3 ms |
16844 KB |
Output is correct |
4 |
Correct |
3 ms |
16732 KB |
Output is correct |
5 |
Correct |
2 ms |
16816 KB |
Output is correct |
6 |
Correct |
3 ms |
16988 KB |
Output is correct |
7 |
Correct |
3 ms |
16732 KB |
Output is correct |
8 |
Correct |
3 ms |
16732 KB |
Output is correct |
9 |
Correct |
3 ms |
16732 KB |
Output is correct |
10 |
Correct |
3 ms |
16872 KB |
Output is correct |
11 |
Correct |
3 ms |
16732 KB |
Output is correct |
12 |
Correct |
4 ms |
16876 KB |
Output is correct |
13 |
Correct |
3 ms |
16732 KB |
Output is correct |
14 |
Correct |
3 ms |
16732 KB |
Output is correct |
15 |
Correct |
2 ms |
16728 KB |
Output is correct |
16 |
Correct |
2 ms |
16732 KB |
Output is correct |
17 |
Correct |
3 ms |
16732 KB |
Output is correct |
18 |
Correct |
3 ms |
16732 KB |
Output is correct |
19 |
Correct |
2 ms |
16732 KB |
Output is correct |
20 |
Correct |
3 ms |
16732 KB |
Output is correct |
21 |
Correct |
3 ms |
16728 KB |
Output is correct |
22 |
Correct |
3 ms |
16732 KB |
Output is correct |
23 |
Correct |
2 ms |
16732 KB |
Output is correct |
24 |
Correct |
2 ms |
16732 KB |
Output is correct |
25 |
Correct |
2 ms |
16732 KB |
Output is correct |
26 |
Correct |
2 ms |
16732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
42700 KB |
Output is correct |
2 |
Correct |
45 ms |
42692 KB |
Output is correct |
3 |
Correct |
47 ms |
42700 KB |
Output is correct |
4 |
Correct |
49 ms |
45892 KB |
Output is correct |
5 |
Correct |
31 ms |
41676 KB |
Output is correct |
6 |
Correct |
30 ms |
41672 KB |
Output is correct |
7 |
Correct |
29 ms |
41684 KB |
Output is correct |
8 |
Correct |
29 ms |
41540 KB |
Output is correct |
9 |
Correct |
106 ms |
43560 KB |
Output is correct |
10 |
Correct |
54 ms |
41296 KB |
Output is correct |
11 |
Correct |
29 ms |
41308 KB |
Output is correct |
12 |
Correct |
25 ms |
41352 KB |
Output is correct |
13 |
Correct |
32 ms |
41680 KB |
Output is correct |
14 |
Correct |
35 ms |
42188 KB |
Output is correct |
15 |
Correct |
43 ms |
42440 KB |
Output is correct |
16 |
Correct |
43 ms |
42600 KB |
Output is correct |
17 |
Correct |
30 ms |
41420 KB |
Output is correct |
18 |
Correct |
32 ms |
41600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
42700 KB |
Output is correct |
2 |
Correct |
52 ms |
42696 KB |
Output is correct |
3 |
Correct |
313 ms |
45548 KB |
Output is correct |
4 |
Correct |
47 ms |
45892 KB |
Output is correct |
5 |
Correct |
280 ms |
41672 KB |
Output is correct |
6 |
Correct |
254 ms |
41680 KB |
Output is correct |
7 |
Correct |
35 ms |
41684 KB |
Output is correct |
8 |
Correct |
196 ms |
41684 KB |
Output is correct |
9 |
Correct |
92 ms |
43716 KB |
Output is correct |
10 |
Correct |
195 ms |
41420 KB |
Output is correct |
11 |
Correct |
218 ms |
41564 KB |
Output is correct |
12 |
Correct |
292 ms |
41364 KB |
Output is correct |
13 |
Correct |
387 ms |
41788 KB |
Output is correct |
14 |
Correct |
402 ms |
44096 KB |
Output is correct |
15 |
Correct |
202 ms |
42816 KB |
Output is correct |
16 |
Correct |
192 ms |
42564 KB |
Output is correct |
17 |
Correct |
201 ms |
41464 KB |
Output is correct |
18 |
Correct |
191 ms |
41464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
363 ms |
161476 KB |
Output is correct |
2 |
Correct |
379 ms |
161472 KB |
Output is correct |
3 |
Correct |
1444 ms |
166164 KB |
Output is correct |
4 |
Correct |
362 ms |
163612 KB |
Output is correct |
5 |
Correct |
870 ms |
155332 KB |
Output is correct |
6 |
Correct |
717 ms |
155476 KB |
Output is correct |
7 |
Correct |
170 ms |
155588 KB |
Output is correct |
8 |
Correct |
600 ms |
155584 KB |
Output is correct |
9 |
Correct |
641 ms |
156028 KB |
Output is correct |
10 |
Correct |
609 ms |
154508 KB |
Output is correct |
11 |
Correct |
698 ms |
154460 KB |
Output is correct |
12 |
Correct |
957 ms |
156312 KB |
Output is correct |
13 |
Correct |
1290 ms |
156100 KB |
Output is correct |
14 |
Correct |
1758 ms |
161912 KB |
Output is correct |
15 |
Correct |
713 ms |
159824 KB |
Output is correct |
16 |
Correct |
716 ms |
159684 KB |
Output is correct |
17 |
Correct |
584 ms |
155328 KB |
Output is correct |
18 |
Correct |
571 ms |
155588 KB |
Output is correct |