# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
792002 |
2023-07-24T13:40:57 Z |
jasmin |
Teams (IOI15_teams) |
C++17 |
|
100 ms |
36092 KB |
#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
struct node{
int left=-1;
int right=-1;
int val=0;
};
struct segtree{
vector<node> tree;
map<int, int> root;
int mom=0;
int build(int l, int r, int v){
tree.push_back({-1, -1, 0});
mom++;
if(l+1==r){
return v;
}
int m=l+(r-l)/2;
tree[v].left = build(l, m, mom);
tree[v].right = build(m, r, mom);
return v;
}
int update(int l, int r, int v, int x){ //returns node index
if(x<l || r<=x) return v;
int momold=mom;
tree.push_back(tree[v]);
tree[mom].val++;
mom++;
int m=l+(r-l)/2;
tree[momold].left = update(l, m, tree[v].left, x);
tree[momold].right = update(m, r, tree[v].right, x);
return momold;
}
int query(int l, int r, int v, int ql, int qr){ //returns sum
if(qr<=l || r<=ql) return 0;
if(ql<=l && r<=qr){
return tree[v].val;
}
int m=l+(r-l)/2;
return query(l, m, tree[v].left, ql, qr) + query(m, r, tree[v].right, ql, qr);
}
};
segtree seg;
int n=0;
void init(int N, int a[], int b[]) {
N++;
n=N;
seg.build(0, n, 0);
seg.root[-1]=0;
vector<int> sorted(n, 0);
iota(sorted.begin(), sorted.end(), 0);
sort(sorted.begin(), sorted.end(), [&](int i, int j){
return a[i]<a[j];
});
int last=0;
for(auto i: sorted){
seg.root[a[i]] = seg.update(0, n, last, b[i]);
last = seg.root[a[i]];
}
}
int can(int m, int K[]) {
vector<int> k(m);
for(int i=0; i<m; i++){
k[i]=K[i];
}
k.push_back(n);
bool pos=true;
int add=0;
for(int i=0; i<m; i++){
int r=seg.root[k[i]];
if(seg.tree[r].val < k[i]+add){
pos=false;
}
int sumuntilnext=seg.query(0, n, 0, k[i], k[i+1]);
add = max(0, k[i]+add - sumuntilnext);
}
if(0<add) pos=false;
return pos;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
18 ms |
7488 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
19 ms |
7568 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
100 ms |
36092 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |