oj.uz

Submission #709952

# Submission time Handle Problem Language Result Execution time Memory
709952 2023-03-15T01:22:00 Z victor_gao Cake 3 (JOI19_cake3) C++17
100 / 100
 1051 ms 210948 KB 
//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 200015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,m,ans=-1e18;
pii arr[N];
struct Node{
    int lch,rch,sum,cnt;
    void pull(Node a,Node b){
        sum=a.sum+b.sum;
        cnt=a.cnt+b.cnt;
    }
    Node(int a=0,int b=0,int c=0,int d=0):lch(a),rch(b),sum(c),cnt(d){}
};
struct lisan{
    vector<int>vt;
    void in(int x){ vt.push_back(x); }
    void build(){
        sort(vt.begin(),vt.end());
        vt.resize(unique(vt.begin(),vt.end())-vt.begin());
    }
    int idx(int x){ return upper_bound(vt.begin(),vt.end(),x)-vt.begin(); }
    int val(int p){ return vt[p-1]; }
}uni;

struct segtree{
    int num=1;
    Node seg[32*N];
    int add(int l,int r,int i,int pos,int c){
        num++; seg[num]=seg[i];
        if (l==r){
            seg[num].cnt++;
            seg[num].sum+=uni.val(l);
            return num;
        }
        int mid=(l+r)>>1,j=num;
        if (pos<=mid) seg[j].lch=add(l,mid,seg[i].lch,pos,c);
        else seg[j].rch=add(mid+1,r,seg[i].rch,pos,c);
        seg[j].pull(seg[seg[j].lch],seg[seg[j].rch]);
        return j;
    }
    int query_pos(int l,int r,int i,int j,int k){
        if (l==r) return l;
        int mid=(l+r)>>1,rc1=seg[i].rch,rc2=seg[j].rch;
        int right_have=seg[rc2].cnt-seg[rc1].cnt;
        if (right_have>=k) return query_pos(mid+1,r,rc1,rc2,k);
        else return query_pos(l,mid,seg[i].lch,seg[j].lch,k-right_have);
    }
    Node query(int l,int r,int i,int j,int ll,int rr){
        // seg[j]-seg[i];
        if (ll<=l&&rr>=r) return Node(0,0,seg[j].sum-seg[i].sum,seg[j].cnt-seg[i].cnt);
        int mid=(l+r)>>1;
        if (rr<=mid) return query(l,mid,seg[i].lch,seg[j].lch,ll,rr);
        else if (ll>mid) return query(mid+1,r,seg[i].rch,seg[j].rch,ll,rr);
        else {
            Node q1=query(l,mid,seg[i].lch,seg[j].lch,ll,rr);
            Node q2=query(mid+1,r,seg[i].rch,seg[j].rch,ll,rr);
            Node ans=Node(); ans.pull(q1,q2);
            return ans;
        }
    }
}seg;
int root[N];
int Query(int l,int r){
    if (r-l+1<m) return -1e18;
    int p=seg.query_pos(1,n,root[l-1],root[r],m),val=uni.val(p);
    Node now=seg.query(1,n,root[l-1],root[r],p,n);
    if (now.cnt>m){
        now.sum=(now.sum-(now.cnt-m)*val);
        now.cnt=m;
    }
    return now.sum-2*(arr[r].y-arr[l].y);
}
void Merge(int l,int r,int ql,int qr){
    if (ql>qr) return;
    if (l==r){
        for (int i=ql;i<=qr;i++)
            ans=max(ans,Query(l,i));
        return;
    }
    int mid=(ql+qr)>>1,best=-1e18,from=l;
    for (int i=l;i<=r;i++){
        int c=Query(i,mid);
        if (c>best){
            best=c;
            from=i;
        }
    }
    ans=max(ans,best);
    Merge(l,from,ql,mid-1);
    Merge(from,r,mid+1,qr);
}

bool cmp(pii a,pii b){
    if (a.y!=b.y) return a.y<b.y;
    return a.x<b.x;
}
signed main(){
    fast
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        cin>>arr[i].x>>arr[i].y;
        uni.in(arr[i].x);
    }
    uni.build();
    for (int i=1;i<=n;i++)
        arr[i].x=uni.idx(arr[i].x);
    sort(arr+1,arr+1+n,cmp);
    for (int i=1;i<=n;i++){
        root[i]=seg.add(1,n,root[i-1],arr[i].x,1);
    }
    Merge(1,n,m,n);
    cout<<ans<<'\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 200748 KB Output is correct
2 Correct 80 ms 200616 KB Output is correct
3 Correct 85 ms 200728 KB Output is correct
4 Correct 86 ms 200652 KB Output is correct
5 Correct 91 ms 200628 KB Output is correct
6 Correct 87 ms 200644 KB Output is correct
7 Correct 77 ms 200688 KB Output is correct
8 Correct 79 ms 200692 KB Output is correct
9 Correct 89 ms 200656 KB Output is correct
10 Correct 80 ms 200652 KB Output is correct
11 Correct 78 ms 200616 KB Output is correct
12 Correct 82 ms 200704 KB Output is correct
13 Correct 84 ms 200652 KB Output is correct
14 Correct 84 ms 200684 KB Output is correct
15 Correct 92 ms 200692 KB Output is correct
16 Correct 79 ms 200680 KB Output is correct
17 Correct 87 ms 200636 KB Output is correct
18 Correct 87 ms 200640 KB Output is correct
19 Correct 82 ms 200628 KB Output is correct
20 Correct 81 ms 200780 KB Output is correct
21 Correct 83 ms 200700 KB Output is correct
22 Correct 81 ms 200652 KB Output is correct
23 Correct 75 ms 200636 KB Output is correct
24 Correct 75 ms 200660 KB Output is correct
25 Correct 89 ms 200628 KB Output is correct
26 Correct 88 ms 200700 KB Output is correct
27 Correct 77 ms 200692 KB Output is correct
28 Correct 77 ms 200676 KB Output is correct
29 Correct 81 ms 200652 KB Output is correct
30 Correct 107 ms 200672 KB Output is correct
31 Correct 80 ms 200652 KB Output is correct
32 Correct 84 ms 200672 KB Output is correct
33 Correct 80 ms 200724 KB Output is correct
34 Correct 81 ms 200696 KB Output is correct
35 Correct 79 ms 200680 KB Output is correct
36 Correct 80 ms 200652 KB Output is correct
37 Correct 82 ms 200632 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 200748 KB Output is correct
2 Correct 80 ms 200616 KB Output is correct
3 Correct 85 ms 200728 KB Output is correct
4 Correct 86 ms 200652 KB Output is correct
5 Correct 91 ms 200628 KB Output is correct
6 Correct 87 ms 200644 KB Output is correct
7 Correct 77 ms 200688 KB Output is correct
8 Correct 79 ms 200692 KB Output is correct
9 Correct 89 ms 200656 KB Output is correct
10 Correct 80 ms 200652 KB Output is correct
11 Correct 78 ms 200616 KB Output is correct
12 Correct 82 ms 200704 KB Output is correct
13 Correct 84 ms 200652 KB Output is correct
14 Correct 84 ms 200684 KB Output is correct
15 Correct 92 ms 200692 KB Output is correct
16 Correct 79 ms 200680 KB Output is correct
17 Correct 87 ms 200636 KB Output is correct
18 Correct 87 ms 200640 KB Output is correct
19 Correct 82 ms 200628 KB Output is correct
20 Correct 81 ms 200780 KB Output is correct
21 Correct 83 ms 200700 KB Output is correct
22 Correct 81 ms 200652 KB Output is correct
23 Correct 75 ms 200636 KB Output is correct
24 Correct 75 ms 200660 KB Output is correct
25 Correct 89 ms 200628 KB Output is correct
26 Correct 88 ms 200700 KB Output is correct
27 Correct 77 ms 200692 KB Output is correct
28 Correct 77 ms 200676 KB Output is correct
29 Correct 81 ms 200652 KB Output is correct
30 Correct 107 ms 200672 KB Output is correct
31 Correct 80 ms 200652 KB Output is correct
32 Correct 84 ms 200672 KB Output is correct
33 Correct 80 ms 200724 KB Output is correct
34 Correct 81 ms 200696 KB Output is correct
35 Correct 79 ms 200680 KB Output is correct
36 Correct 80 ms 200652 KB Output is correct
37 Correct 82 ms 200632 KB Output is correct
38 Correct 84 ms 200756 KB Output is correct
39 Correct 86 ms 200740 KB Output is correct
40 Correct 82 ms 200780 KB Output is correct
41 Correct 83 ms 200800 KB Output is correct
42 Correct 90 ms 200824 KB Output is correct
43 Correct 93 ms 200704 KB Output is correct
44 Correct 84 ms 200820 KB Output is correct
45 Correct 85 ms 200800 KB Output is correct
46 Correct 86 ms 200772 KB Output is correct
47 Correct 94 ms 200772 KB Output is correct
48 Correct 83 ms 200724 KB Output is correct
49 Correct 84 ms 200864 KB Output is correct
50 Correct 90 ms 200732 KB Output is correct
51 Correct 106 ms 200772 KB Output is correct
52 Correct 85 ms 200740 KB Output is correct
53 Correct 82 ms 200796 KB Output is correct
54 Correct 83 ms 200832 KB Output is correct
55 Correct 87 ms 200720 KB Output is correct
56 Correct 82 ms 200780 KB Output is correct
57 Correct 94 ms 200772 KB Output is correct
58 Correct 103 ms 200724 KB Output is correct
59 Correct 83 ms 200800 KB Output is correct
60 Correct 81 ms 200720 KB Output is correct
61 Correct 82 ms 200724 KB Output is correct
62 Correct 97 ms 200764 KB Output is correct
63 Correct 91 ms 200888 KB Output is correct
64 Correct 82 ms 200728 KB Output is correct
65 Correct 84 ms 200788 KB Output is correct
66 Correct 87 ms 200844 KB Output is correct
67 Correct 85 ms 200784 KB Output is correct
68 Correct 84 ms 200780 KB Output is correct
69 Correct 81 ms 200744 KB Output is correct
70 Correct 80 ms 200800 KB Output is correct
71 Correct 89 ms 200744 KB Output is correct
72 Correct 87 ms 200724 KB Output is correct
73 Correct 89 ms 200832 KB Output is correct
74 Correct 80 ms 200780 KB Output is correct

Subtask #3
76.0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 200748 KB Output is correct
2 Correct 80 ms 200616 KB Output is correct
3 Correct 85 ms 200728 KB Output is correct
4 Correct 86 ms 200652 KB Output is correct
5 Correct 91 ms 200628 KB Output is correct
6 Correct 87 ms 200644 KB Output is correct
7 Correct 77 ms 200688 KB Output is correct
8 Correct 79 ms 200692 KB Output is correct
9 Correct 89 ms 200656 KB Output is correct
10 Correct 80 ms 200652 KB Output is correct
11 Correct 78 ms 200616 KB Output is correct
12 Correct 82 ms 200704 KB Output is correct
13 Correct 84 ms 200652 KB Output is correct
14 Correct 84 ms 200684 KB Output is correct
15 Correct 92 ms 200692 KB Output is correct
16 Correct 79 ms 200680 KB Output is correct
17 Correct 87 ms 200636 KB Output is correct
18 Correct 87 ms 200640 KB Output is correct
19 Correct 82 ms 200628 KB Output is correct
20 Correct 81 ms 200780 KB Output is correct
21 Correct 83 ms 200700 KB Output is correct
22 Correct 81 ms 200652 KB Output is correct
23 Correct 75 ms 200636 KB Output is correct
24 Correct 75 ms 200660 KB Output is correct
25 Correct 89 ms 200628 KB Output is correct
26 Correct 88 ms 200700 KB Output is correct
27 Correct 77 ms 200692 KB Output is correct
28 Correct 77 ms 200676 KB Output is correct
29 Correct 81 ms 200652 KB Output is correct
30 Correct 107 ms 200672 KB Output is correct
31 Correct 80 ms 200652 KB Output is correct
32 Correct 84 ms 200672 KB Output is correct
33 Correct 80 ms 200724 KB Output is correct
34 Correct 81 ms 200696 KB Output is correct
35 Correct 79 ms 200680 KB Output is correct
36 Correct 80 ms 200652 KB Output is correct
37 Correct 82 ms 200632 KB Output is correct
38 Correct 84 ms 200756 KB Output is correct
39 Correct 86 ms 200740 KB Output is correct
40 Correct 82 ms 200780 KB Output is correct
41 Correct 83 ms 200800 KB Output is correct
42 Correct 90 ms 200824 KB Output is correct
43 Correct 93 ms 200704 KB Output is correct
44 Correct 84 ms 200820 KB Output is correct
45 Correct 85 ms 200800 KB Output is correct
46 Correct 86 ms 200772 KB Output is correct
47 Correct 94 ms 200772 KB Output is correct
48 Correct 83 ms 200724 KB Output is correct
49 Correct 84 ms 200864 KB Output is correct
50 Correct 90 ms 200732 KB Output is correct
51 Correct 106 ms 200772 KB Output is correct
52 Correct 85 ms 200740 KB Output is correct
53 Correct 82 ms 200796 KB Output is correct
54 Correct 83 ms 200832 KB Output is correct
55 Correct 87 ms 200720 KB Output is correct
56 Correct 82 ms 200780 KB Output is correct
57 Correct 94 ms 200772 KB Output is correct
58 Correct 103 ms 200724 KB Output is correct
59 Correct 83 ms 200800 KB Output is correct
60 Correct 81 ms 200720 KB Output is correct
61 Correct 82 ms 200724 KB Output is correct
62 Correct 97 ms 200764 KB Output is correct
63 Correct 91 ms 200888 KB Output is correct
64 Correct 82 ms 200728 KB Output is correct
65 Correct 84 ms 200788 KB Output is correct
66 Correct 87 ms 200844 KB Output is correct
67 Correct 85 ms 200784 KB Output is correct
68 Correct 84 ms 200780 KB Output is correct
69 Correct 81 ms 200744 KB Output is correct
70 Correct 80 ms 200800 KB Output is correct
71 Correct 89 ms 200744 KB Output is correct
72 Correct 87 ms 200724 KB Output is correct
73 Correct 89 ms 200832 KB Output is correct
74 Correct 80 ms 200780 KB Output is correct
75 Correct 861 ms 210260 KB Output is correct
76 Correct 1051 ms 210012 KB Output is correct
77 Correct 815 ms 210264 KB Output is correct
78 Correct 867 ms 210352 KB Output is correct
79 Correct 319 ms 210428 KB Output is correct
80 Correct 317 ms 210176 KB Output is correct
81 Correct 653 ms 209596 KB Output is correct
82 Correct 823 ms 209728 KB Output is correct
83 Correct 740 ms 209936 KB Output is correct
84 Correct 733 ms 210016 KB Output is correct
85 Correct 637 ms 209576 KB Output is correct
86 Correct 387 ms 209412 KB Output is correct
87 Correct 414 ms 209184 KB Output is correct
88 Correct 628 ms 209220 KB Output is correct
89 Correct 574 ms 209616 KB Output is correct
90 Correct 422 ms 209952 KB Output is correct
91 Correct 318 ms 209384 KB Output is correct
92 Correct 318 ms 209276 KB Output is correct
93 Correct 384 ms 209668 KB Output is correct
94 Correct 298 ms 209988 KB Output is correct
95 Correct 405 ms 209988 KB Output is correct
96 Correct 277 ms 209292 KB Output is correct
97 Correct 281 ms 209928 KB Output is correct
98 Correct 279 ms 209848 KB Output is correct
99 Correct 261 ms 209856 KB Output is correct
100 Correct 251 ms 209380 KB Output is correct
101 Correct 237 ms 209372 KB Output is correct
102 Correct 641 ms 209392 KB Output is correct
103 Correct 598 ms 209268 KB Output is correct
104 Correct 743 ms 209688 KB Output is correct
105 Correct 474 ms 209688 KB Output is correct
106 Correct 515 ms 209856 KB Output is correct
107 Correct 445 ms 209560 KB Output is correct
108 Correct 789 ms 210172 KB Output is correct
109 Correct 679 ms 210816 KB Output is correct
110 Correct 238 ms 208852 KB Output is correct
111 Correct 369 ms 208944 KB Output is correct
112 Correct 665 ms 208548 KB Output is correct
113 Correct 291 ms 210948 KB Output is correct