oj.uz

Submission #671101

# Submission time Handle Problem Language Result Execution time Memory
671101 2022-12-12T02:59:31 Z victor_gao Teams (IOI15_teams) C++17
100 / 100
 1237 ms 345716 KB 
#include <bits/stdc++.h>
#include "teams.h"
#define pii pair<int,int>
#define x first
#define y second
#define MAXN 500005
using namespace std;
int L[MAXN],R[MAXN],n,root[MAXN];
struct Node{
    int l,r,lch,rch,val;
    Node(int _l=0,int _r=0,int a=0,int b=0,int c=0):l(_l),r(_r),lch(a),rch(b),val(c){}
};
struct segtree{
    vector<Node>seg;
    int num=0;
    int add_node(int l,int r){
        seg.push_back(Node(l,r,0,0,0));
        return num++;
    }
    void build(int i){
        int l=seg[i].l,r=seg[i].r,mid=(l+r)>>1;
        if (l==r) return;
        seg[i].lch=add_node(l,mid);
        seg[i].rch=add_node(mid+1,r);
        build(seg[i].lch); build(seg[i].rch);
    }
    void Insert(int i,int j,int p,int c){
        int l=seg[i].l,r=seg[i].r,mid=(l+r)>>1;
        if (l==r){
            seg[i].val+=c;
            return;
        }
        if (p<=mid){
            seg[i].lch=add_node(l,mid); seg[i].rch=seg[j].rch;
            seg[seg[i].lch]=seg[seg[j].lch];
            Insert(seg[i].lch,seg[j].lch,p,c);
            seg[i].val=seg[seg[i].lch].val+seg[seg[i].rch].val;
        } 
        else {
            seg[i].rch=add_node(mid+1,r); seg[i].lch=seg[j].lch;
            seg[seg[i].rch]=seg[seg[j].rch];
            Insert(seg[i].rch,seg[j].rch,p,c);
            seg[i].val=seg[seg[i].rch].val+seg[seg[i].lch].val;
        }
    }
    int query(int i,int j,int ll,int rr){
        // 計算 版本 i~j ll~rr 點的個數
        // 也就是 L1~L2 ll<=R<=rr 的點的個數
        int l=seg[i].l,r=seg[i].r,mid=(l+r)>>1;
        if (ll>rr) return 0;
        if (ll<=l&&rr>=r)
            return seg[i].val-seg[j].val;
        if (rr<=mid) return query(seg[i].lch,seg[j].lch,ll,rr);
        else if (ll>mid) return query(seg[i].rch,seg[j].rch,ll,rr);
        else return query(seg[i].lch,seg[j].lch,ll,mid)+query(seg[i].rch,seg[j].rch,mid+1,rr);
    }
    int query_pos(int i,int j,int need){
        int l=seg[i].l,r=seg[i].r;
        if (l==r) return l;
        int tmp=seg[seg[i].lch].val-seg[seg[j].lch].val;
        if (tmp<need) return query_pos(seg[i].rch,seg[j].rch,need-tmp);
        else return query_pos(seg[i].lch,seg[j].lch,need);
    }
    void debug(int i){
        cout<<seg[i].l<<" "<<seg[i].r<<" -> "<<seg[i].val<<'\n';
        if (seg[i].l==seg[i].r)
            return;
        debug(seg[i].lch); debug(seg[i].rch);
    }
}seg;
void init(int N, int A[], int B[]) {
    n=N;
    vector<pii>all;
    for (int i=1;i<=n;i++){
        L[i]=A[i-1]; R[i]=B[i-1];
        all.push_back({L[i],R[i]});
    }
    sort(all.begin(),all.end());
    root[0]=seg.add_node(1,n+1);
    seg.build(0);
    for (int i=1,j=0;i<=n;i++){
        root[i]=root[i-1];
        while (j<n&&all[j].x==i){
            int nrt=seg.add_node(1,n+1);
            seg.Insert(nrt,root[i],all[j].y,1);
            root[i]=nrt; j++;
        }
    }
}
int H[MAXN],last[MAXN],K[MAXN];
int can(int M, int NK[]) {
    for (int i=0;i<=M+5;i++){
        last[i]=0; H[i]=0; K[i]=0;
    }
    H[0]=n+1;
    for (int i=1;i<=M;i++)
        K[i]=NK[i-1];
    sort(K+1,K+1+M);
    vector<int>st;
    for (int i=1;i<=M;i++){
        while (!st.empty()&&H[st.back()]<K[i]) st.pop_back();
        int need=K[i]; last[i]=0; H[i]=K[i]-1;
        if (K[i]>n) return 0;
        while (!st.empty()){
            int j=st.back();
            int h=H[j];
            if (K[i]==K[j]){
                H[i]=H[j]; last[i]=last[j];
                st.pop_back();
                continue;
            }
            int get=seg.query(root[K[i]],root[K[j]],H[i]+1,h)+last[j]+last[i];
            if (get<need){
                need-=get; H[i]=h; last[i]=0;
                st.pop_back();
            }
            else break;
        }
        int j=(st.empty()) ? 0 : st.back();
        int out=seg.query(root[K[i]],root[K[j]],1,H[i]);
        int l=seg.query_pos(root[K[i]],root[K[j]],out+need-last[i]);
        l=min(l,H[j]);
     //   cout<<j<<" -> "<<out<<" "<<need<<" "<<last[i]<<'\n';
        /*
        int l=H[i],r=H[j];
        while (l<r){
            int mid=(l+r)>>1;
            int val=seg.query(root[K[i]],root[K[j]],H[i]+1,mid)+last[i];
            if (val>=need) r=mid;
            else l=mid+1;
        }
        */
        int can_use=seg.query(root[K[i]],root[K[j]],H[i]+1,l)+last[i];
        H[i]=l;
        while (!st.empty()&&H[i]==H[st.back()]){
            can_use+=last[st.back()];
            st.pop_back();
        }
        last[i]=can_use-need;
      //  cout<<i<<" "<<K[i]<<" : "<<H[i]<<' '<<last[i]<<'\n';
        if (can_use<need)
            return 0;
        st.push_back(i);
    }
    return 1;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 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 312 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 316 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 312 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 44444 KB Output is correct
2 Correct 114 ms 44384 KB Output is correct
3 Correct 100 ms 44412 KB Output is correct
4 Correct 103 ms 44428 KB Output is correct
5 Correct 75 ms 44300 KB Output is correct
6 Correct 73 ms 44304 KB Output is correct
7 Correct 74 ms 44384 KB Output is correct
8 Correct 76 ms 44272 KB Output is correct
9 Correct 80 ms 44360 KB Output is correct
10 Correct 70 ms 44344 KB Output is correct
11 Correct 72 ms 44872 KB Output is correct
12 Correct 71 ms 45056 KB Output is correct
13 Correct 76 ms 45324 KB Output is correct
14 Correct 80 ms 45268 KB Output is correct
15 Correct 107 ms 45532 KB Output is correct
16 Correct 95 ms 45536 KB Output is correct
17 Correct 75 ms 45448 KB Output is correct
18 Correct 76 ms 45480 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 44424 KB Output is correct
2 Correct 110 ms 44500 KB Output is correct
3 Correct 265 ms 44388 KB Output is correct
4 Correct 101 ms 44448 KB Output is correct
5 Correct 108 ms 44332 KB Output is correct
6 Correct 109 ms 44360 KB Output is correct
7 Correct 80 ms 44348 KB Output is correct
8 Correct 99 ms 44364 KB Output is correct
9 Correct 80 ms 44348 KB Output is correct
10 Correct 93 ms 44340 KB Output is correct
11 Correct 94 ms 45124 KB Output is correct
12 Correct 118 ms 45216 KB Output is correct
13 Correct 171 ms 45284 KB Output is correct
14 Correct 321 ms 45356 KB Output is correct
15 Correct 126 ms 45628 KB Output is correct
16 Correct 127 ms 45488 KB Output is correct
17 Correct 105 ms 45512 KB Output is correct
18 Correct 109 ms 45456 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 702 ms 343828 KB Output is correct
2 Correct 692 ms 343864 KB Output is correct
3 Correct 1185 ms 343896 KB Output is correct
4 Correct 676 ms 343848 KB Output is correct
5 Correct 538 ms 343000 KB Output is correct
6 Correct 507 ms 342852 KB Output is correct
7 Correct 448 ms 342888 KB Output is correct
8 Correct 504 ms 342960 KB Output is correct
9 Correct 457 ms 342884 KB Output is correct
10 Correct 454 ms 342888 KB Output is correct
11 Correct 479 ms 344768 KB Output is correct
12 Correct 556 ms 344560 KB Output is correct
13 Correct 808 ms 344668 KB Output is correct
14 Correct 1237 ms 345412 KB Output is correct
15 Correct 677 ms 345716 KB Output is correct
16 Correct 709 ms 345376 KB Output is correct
17 Correct 513 ms 345108 KB Output is correct
18 Correct 510 ms 345208 KB Output is correct