oj.uz

Submission #1089134

# Submission time Handle Problem Language Result Execution time Memory
1089134 2024-09-16T05:34:54 Z guagua0407 Teams (IOI15_teams) C++17
100 / 100
 818 ms 150364 KB 
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int mxn=5e5+5;
const int inf=1e9;
vector<int> segtree(mxn*20);
vector<int> R(mxn*20),L(mxn*20);
vector<int> root(mxn);
int n;
int cnt=0;

int update(int node,int pos,int l=1,int r=n){
    int x=++cnt;
    assert(x<mxn*20);
    L[x]=L[node];
    R[x]=R[node];
    segtree[x]=segtree[node];
    if(l==r){
        segtree[x]++;
        return x;
    }
    int mid=(l+r)/2;
    if(pos<=mid) L[x]=update(L[node],pos,l,mid);
    else R[x]=update(R[node],pos,mid+1,r);
    segtree[x]=segtree[L[x]]+segtree[R[x]];
    return x;
}

int query(int node1,int node2,int tl,int tr,int l=1,int r=n){
    if(r<tl or tr<l){
        return 0;
    }
    if(tl<=l and r<=tr){
        return segtree[node1]-segtree[node2];
    }
    int mid=(l+r)/2;
    return query(L[node1],L[node2],tl,min(mid,tr),l,mid)+query(R[node1],R[node2],max(mid+1,tl),tr,mid+1,r);
}

int kth(int node1,int node2,int k,int l=1,int r=n){
    if(l==r){
        return l;
    }
    int sum=segtree[L[node1]]-segtree[L[node2]];
    int mid=(l+r)/2;
    if(k<=sum) return kth(L[node1],L[node2],k,l,mid);
    else return kth(R[node1],R[node2],k-sum,mid+1,r);
}


void init(int N, int A[], int B[]) {
    n=N;
    vector<vector<int>> vec(n+1);
    for(int i=0;i<n;i++){
        vec[A[i]].push_back(B[i]);
    }
    for(int i=1;i<=n;i++){
        root[i]=root[i-1];
        for(auto v:vec[i]){
            root[i]=update(root[i],v);
        }
    }
}

int can(int M, int K[]) {
    sort(K,K+M);
    int m=M+1;
    vector<int> vec(m);
    for(int i=1;i<m;i++){
        vec[i]=K[i-1];
    }
    vector<int> rem(m);
    vector<int> used(m);
    vector<int> H(m);
    vector<int> st;
    st.push_back(0);
    H[0]=n+1;
    //cout<<'\n';
    for(int i=1;i<m;i++){
        used[i]=query(root[vec[i]],root[vec[st.back()]],1,vec[i]-1);
        while(!st.empty() and H[st.back()]<vec[i]){
            used[i]+=query(root[vec[st.back()]],root[vec[st[st.size()-2]]],1,vec[i]-1);
            st.pop_back();
        }
        int sum=rem[st.back()]+query(root[vec[i]],root[vec[st.back()]],1,n)-used[i];
        //cout<<sum<<' '<<rem[st.back()]<<' '<<query(root[vec[i]],root[vec[st.back()]],vec[i],n)<<'\n';
        if(sum<vec[i]){
            return 0;
        }
        H[i]=vec[i];
        int cur=vec[i];
        while(!st.empty()){
            int now=query(root[vec[i]],root[vec[st.back()]],1,H[st.back()]-1)-used[i];
            //cout<<now<<'\n';
            if(now>=cur){
                used[i]+=cur;
                if(now==cur) H[i]=H[st.back()];
                else H[i]=kth(root[vec[i]],root[vec[st.back()]],used[i]+1);
                assert(H[i]<=H[st.back()]);
                rem[i]=rem[st.back()]+query(root[vec[i]],root[vec[st.back()]],1,n)-used[i];
                break;
            }
            else{
                H[i]=H[st.back()];
                used[i]+=used[st.back()];
                used[i]+=now;
                cur-=now;
                st.pop_back();
            }
        }
        if(H[st.back()]==H[i]){
            used[i]+=used[st.back()];
            st.pop_back();
        }
        st.push_back(i);
    }
	return 1;
}

/*int main() {
    int N;
    cin>>N;
    int *A = (int*)malloc(sizeof(int)*(unsigned int)N);
    int *B = (int*)malloc(sizeof(int)*(unsigned int)N);
    for (int i = 0; i < N; ++i) {
    	cin>>A[i]>>B[i];
    }
    init(N, A, B);
    int Q;
    cin>>Q;
    for (int i = 0; i < Q; ++i) {
    	int M;
    	cin>>M;
	int *K = (int*)malloc(sizeof(int)*(unsigned int)M);
    	for (int j = 0; j < M; ++j) {
    		cin>>K[j];
    	}
    	cout<<can(M, K)<<'\n';
    }
    return 0;
}*/

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 119568 KB Output is correct
2 Correct 39 ms 119588 KB Output is correct
3 Correct 39 ms 119632 KB Output is correct
4 Correct 40 ms 119632 KB Output is correct
5 Correct 39 ms 119632 KB Output is correct
6 Correct 39 ms 119888 KB Output is correct
7 Correct 40 ms 119632 KB Output is correct
8 Correct 39 ms 119644 KB Output is correct
9 Correct 40 ms 119640 KB Output is correct
10 Correct 39 ms 119596 KB Output is correct
11 Correct 40 ms 119692 KB Output is correct
12 Correct 45 ms 119636 KB Output is correct
13 Correct 47 ms 119676 KB Output is correct
14 Correct 41 ms 119636 KB Output is correct
15 Correct 39 ms 119632 KB Output is correct
16 Correct 40 ms 119636 KB Output is correct
17 Correct 39 ms 119576 KB Output is correct
18 Correct 43 ms 119636 KB Output is correct
19 Correct 44 ms 119636 KB Output is correct
20 Correct 43 ms 119612 KB Output is correct
21 Correct 42 ms 119632 KB Output is correct
22 Correct 46 ms 119628 KB Output is correct
23 Correct 46 ms 119800 KB Output is correct
24 Correct 43 ms 119888 KB Output is correct
25 Correct 42 ms 119652 KB Output is correct
26 Correct 45 ms 119632 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 125268 KB Output is correct
2 Correct 84 ms 125268 KB Output is correct
3 Correct 80 ms 125264 KB Output is correct
4 Correct 90 ms 125568 KB Output is correct
5 Correct 62 ms 124244 KB Output is correct
6 Correct 61 ms 124412 KB Output is correct
7 Correct 61 ms 124408 KB Output is correct
8 Correct 61 ms 124332 KB Output is correct
9 Correct 72 ms 124212 KB Output is correct
10 Correct 64 ms 124116 KB Output is correct
11 Correct 59 ms 123856 KB Output is correct
12 Correct 62 ms 123852 KB Output is correct
13 Correct 69 ms 124500 KB Output is correct
14 Correct 67 ms 124892 KB Output is correct
15 Correct 79 ms 125164 KB Output is correct
16 Correct 75 ms 125264 KB Output is correct
17 Correct 60 ms 124244 KB Output is correct
18 Correct 66 ms 124160 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 125520 KB Output is correct
2 Correct 84 ms 125396 KB Output is correct
3 Correct 144 ms 125704 KB Output is correct
4 Correct 88 ms 125556 KB Output is correct
5 Correct 78 ms 123984 KB Output is correct
6 Correct 76 ms 124156 KB Output is correct
7 Correct 65 ms 123984 KB Output is correct
8 Correct 76 ms 123984 KB Output is correct
9 Correct 69 ms 124108 KB Output is correct
10 Correct 83 ms 124108 KB Output is correct
11 Correct 88 ms 124108 KB Output is correct
12 Correct 90 ms 123852 KB Output is correct
13 Correct 127 ms 124500 KB Output is correct
14 Correct 167 ms 125104 KB Output is correct
15 Correct 93 ms 125396 KB Output is correct
16 Correct 95 ms 125264 KB Output is correct
17 Correct 87 ms 124500 KB Output is correct
18 Correct 82 ms 124324 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 148304 KB Output is correct
2 Correct 358 ms 148304 KB Output is correct
3 Correct 818 ms 148048 KB Output is correct
4 Correct 371 ms 150364 KB Output is correct
5 Correct 194 ms 141804 KB Output is correct
6 Correct 181 ms 142036 KB Output is correct
7 Correct 150 ms 141908 KB Output is correct
8 Correct 171 ms 141904 KB Output is correct
9 Correct 179 ms 141268 KB Output is correct
10 Correct 178 ms 139972 KB Output is correct
11 Correct 198 ms 140272 KB Output is correct
12 Correct 210 ms 140740 KB Output is correct
13 Correct 377 ms 143040 KB Output is correct
14 Correct 803 ms 148240 KB Output is correct
15 Correct 313 ms 148372 KB Output is correct
16 Correct 310 ms 148172 KB Output is correct
17 Correct 186 ms 142588 KB Output is correct
18 Correct 185 ms 142868 KB Output is correct