# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1063667 |
2024-08-17T22:46:35 Z |
nishkarsh |
Teams (IOI15_teams) |
C++14 |
|
664 ms |
154128 KB |
#include <bits/stdc++.h>
#define ll long long
#define vt vector
#define pb push_back
using namespace std;
int fastexp(int b, int e, int mod){
int ans = 1;
while(e){
if(e&1) ans = (1ll*ans*b)%mod;
b = (1ll*b*b)%mod;
e >>= 1;
}
return ans;
}
const int N = 5e5+1;
const int mod = 998244353;
const ll INFLL = 1e18;
const int INF = 2e9;
const int logn = 20;
struct pers_segtree_node{
int lt,rt,val;
};
int pers_segtree_nodecnt = 0;
pers_segtree_node pers_segtree[N*logn];
int update(int node, int i, int j, int ind){
int nw_node = ++pers_segtree_nodecnt;
pers_segtree[nw_node] = pers_segtree[node];
pers_segtree[nw_node].val++;
if(i == j) return nw_node;
int mid = (i+j) / 2;
if(ind <= mid) pers_segtree[nw_node].lt = update(pers_segtree[node].lt, i, mid, ind);
else pers_segtree[nw_node].rt = update(pers_segtree[node].rt, mid+1, j, ind);
return nw_node;
}
struct my_segtree_node{
int curr, latest, last_exhausted, vis;
};
int my_segtree_nodecnt;
my_segtree_node my_segtree[4*N];
void query(int node, int i, int j, int l, int r, int pers_segtree_node_num, int tim, int &val){
my_segtree[node].vis = 1;
if(val == 0 || pers_segtree_node_num == 0 || i > r || l > j || i > j || l > r) return;
if(i >= l && j <= r){
// cout << pers_segtree[pers_segtree_node_num].val << " " << my_segtree[node].curr << " " << i << " " << j << " " << l << " " << r << "\n";
int left = pers_segtree[pers_segtree_node_num].val - pers_segtree[my_segtree[node].latest].val - my_segtree[node].curr;
if(val >= left){
val -= left;
my_segtree[node].latest = pers_segtree_node_num;
my_segtree[node].last_exhausted = tim;
my_segtree[node].curr = 0;
return;
}
else{
my_segtree[node].curr += val;
if(i == j) val = 0;
}
}
if(i == j) return;
int mid = (i+j) / 2;
if(my_segtree[2*node].last_exhausted < my_segtree[node].last_exhausted){
my_segtree[2*node].last_exhausted = my_segtree[node].last_exhausted;
my_segtree[2*node].curr = 0;
my_segtree[2*node].latest = pers_segtree[my_segtree[node].latest].lt;
}
query(2*node, i, mid, l, r, pers_segtree[pers_segtree_node_num].lt, tim, val);
if(my_segtree[2*node+1].last_exhausted < my_segtree[node].last_exhausted){
my_segtree[2*node+1].last_exhausted = my_segtree[node].last_exhausted;
my_segtree[2*node+1].curr = 0;
my_segtree[2*node+1].latest = pers_segtree[my_segtree[node].latest].rt;
}
query(2*node+1, mid+1, j, l, r, pers_segtree[pers_segtree_node_num].rt, tim, val);
}
void clear_my_segtree(int node, int i, int j){
if(! my_segtree[node].vis) return;
my_segtree[node] = {0,0,0,0};
if(i==j) return;
int mid = (i+j)/2;
clear_my_segtree(2*node,i,mid);
clear_my_segtree(2*node + 1,mid+1,j);
}
int times[N];
int n;
void init(int N, int *A, int *B){
n = N;
vt<vt<int>> ranges(n+1);
for(int i = 0; i < n; i++) ranges[A[i]].pb(B[i]);
for(int i = 1; i <= n; i++){
times[i] = times[i-1];
for(int j : ranges[i]) times[i] = update(times[i], 1, N, j);
}
}
bool can(int M, int *K){
sort(K,K+M);
for(int i = 0; i < M; i++){
int temp_val = K[i];
query(1,1,n,K[i],n,times[K[i]],i+1,temp_val);
// cout << times[K[i]] << " " << K[i] << " " << temp_val << "\n";
if(temp_val > 0){
clear_my_segtree(1,1,n);
return false;
}
}
clear_my_segtree(1,1,n);
return true;
}
void solve(){
int n;
cin >> n;
int A[n],B[n];
for(int i = 0; i < n; i++) cin >> A[i] >> B[i];
init(n,A,B);
int q,k;
cin >> q;
while(q--){
cin >> k;
int temp[k];
for(int i = 0; i < k; i++) cin >> temp[i];
cout << can(k,temp) << "\n";
}
}
// int main()
// {
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// int t = 1;
// // cin >> t;
// while(t--){
// solve();
// }
// return 0;
// }
Compilation message
teams.cpp: In function 'int fastexp(int, int, int)':
teams.cpp:10:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
10 | if(e&1) ans = (1ll*ans*b)%mod;
| ~~~~~~~~~~~^~~~
teams.cpp:11:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
11 | b = (1ll*b*b)%mod;
| ~~~~~~~~~^~~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:101:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
101 | void init(int N, int *A, int *B){
| ~~~~^
teams.cpp:17:11: note: shadowed declaration is here
17 | const int N = 5e5+1;
| ^
teams.cpp: In function 'void solve()':
teams.cpp:128:6: warning: declaration of 'n' shadows a global declaration [-Wshadow]
128 | int n;
| ^
teams.cpp:99:5: note: shadowed declaration is here
99 | int n;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
0 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
0 ms |
2396 KB |
Output is correct |
7 |
Correct |
0 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
0 ms |
2396 KB |
Output is correct |
10 |
Correct |
0 ms |
2396 KB |
Output is correct |
11 |
Correct |
0 ms |
2396 KB |
Output is correct |
12 |
Correct |
1 ms |
2396 KB |
Output is correct |
13 |
Correct |
1 ms |
2396 KB |
Output is correct |
14 |
Correct |
1 ms |
2396 KB |
Output is correct |
15 |
Correct |
0 ms |
2488 KB |
Output is correct |
16 |
Correct |
1 ms |
2396 KB |
Output is correct |
17 |
Correct |
1 ms |
2652 KB |
Output is correct |
18 |
Correct |
1 ms |
2396 KB |
Output is correct |
19 |
Correct |
0 ms |
2396 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
2396 KB |
Output is correct |
23 |
Correct |
1 ms |
2396 KB |
Output is correct |
24 |
Correct |
1 ms |
2396 KB |
Output is correct |
25 |
Correct |
1 ms |
2396 KB |
Output is correct |
26 |
Correct |
1 ms |
2392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
26452 KB |
Output is correct |
2 |
Correct |
35 ms |
26448 KB |
Output is correct |
3 |
Correct |
31 ms |
26300 KB |
Output is correct |
4 |
Correct |
33 ms |
26460 KB |
Output is correct |
5 |
Correct |
17 ms |
25436 KB |
Output is correct |
6 |
Correct |
14 ms |
25436 KB |
Output is correct |
7 |
Correct |
15 ms |
25328 KB |
Output is correct |
8 |
Correct |
14 ms |
25228 KB |
Output is correct |
9 |
Correct |
23 ms |
24276 KB |
Output is correct |
10 |
Correct |
17 ms |
24788 KB |
Output is correct |
11 |
Correct |
14 ms |
26068 KB |
Output is correct |
12 |
Correct |
15 ms |
25044 KB |
Output is correct |
13 |
Correct |
21 ms |
26584 KB |
Output is correct |
14 |
Correct |
24 ms |
26068 KB |
Output is correct |
15 |
Correct |
29 ms |
27472 KB |
Output is correct |
16 |
Correct |
30 ms |
27472 KB |
Output is correct |
17 |
Correct |
17 ms |
26716 KB |
Output is correct |
18 |
Correct |
18 ms |
26608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
26340 KB |
Output is correct |
2 |
Correct |
35 ms |
26456 KB |
Output is correct |
3 |
Correct |
116 ms |
29612 KB |
Output is correct |
4 |
Correct |
30 ms |
26448 KB |
Output is correct |
5 |
Correct |
33 ms |
25432 KB |
Output is correct |
6 |
Correct |
33 ms |
25432 KB |
Output is correct |
7 |
Correct |
18 ms |
25436 KB |
Output is correct |
8 |
Correct |
27 ms |
25436 KB |
Output is correct |
9 |
Correct |
25 ms |
25044 KB |
Output is correct |
10 |
Correct |
29 ms |
25040 KB |
Output is correct |
11 |
Correct |
34 ms |
26380 KB |
Output is correct |
12 |
Correct |
44 ms |
25204 KB |
Output is correct |
13 |
Correct |
73 ms |
26828 KB |
Output is correct |
14 |
Correct |
118 ms |
29868 KB |
Output is correct |
15 |
Correct |
44 ms |
27612 KB |
Output is correct |
16 |
Correct |
45 ms |
27476 KB |
Output is correct |
17 |
Correct |
35 ms |
26712 KB |
Output is correct |
18 |
Correct |
46 ms |
26840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
261 ms |
143956 KB |
Output is correct |
2 |
Correct |
258 ms |
143956 KB |
Output is correct |
3 |
Correct |
568 ms |
149128 KB |
Output is correct |
4 |
Correct |
241 ms |
144092 KB |
Output is correct |
5 |
Correct |
134 ms |
138116 KB |
Output is correct |
6 |
Correct |
133 ms |
138064 KB |
Output is correct |
7 |
Correct |
100 ms |
138104 KB |
Output is correct |
8 |
Correct |
124 ms |
138280 KB |
Output is correct |
9 |
Correct |
137 ms |
136128 KB |
Output is correct |
10 |
Correct |
119 ms |
139972 KB |
Output is correct |
11 |
Correct |
129 ms |
140536 KB |
Output is correct |
12 |
Correct |
169 ms |
141124 KB |
Output is correct |
13 |
Correct |
321 ms |
144068 KB |
Output is correct |
14 |
Correct |
664 ms |
154128 KB |
Output is correct |
15 |
Correct |
248 ms |
149068 KB |
Output is correct |
16 |
Correct |
231 ms |
149232 KB |
Output is correct |
17 |
Correct |
143 ms |
143720 KB |
Output is correct |
18 |
Correct |
139 ms |
143756 KB |
Output is correct |