oj.uz

Submission #917668

# Submission time Handle Problem Language Result Execution time Memory
917668 2024-01-28T14:35:13 Z bachhoangxuan Ants and Sugar (JOI22_sugar) C++17
100 / 100
 3447 ms 205440 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
const int maxn=500005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
const int base=131;
const int S=2;

int q,L;
struct query{
    int t,x,a;
}qq[maxn];

int sz;
vector<int> com;
int get_pos(int x){
    return lower_bound(com.begin(),com.end(),x)-com.begin()+1;
}

int C[8*maxn],D[8*maxn],tree[8*maxn][2][2][S];


void getnew(int id,int c,int d){
    for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<S;k++) if(tree[id][i][j][k]!=-inf) tree[id][i][j][k]+=i*c-j*d+k*(c-d);
    C[id]+=c;D[id]+=d;
}
void pushdown(int id){
    if(!C[id] && !D[id]) return;
    getnew(id<<1,C[id],D[id]);
    getnew(id<<1|1,C[id],D[id]);
    C[id]=D[id]=0;
}

void merge(int id){
    for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<S;k++){
        tree[id][i][j][k]=max(tree[id<<1][i][j][k],tree[id<<1|1][i][j][k]);
    }
    for(int li=0;li<2;li++) for(int lj=0;lj<2;lj++) for(int rj=0;rj<2;rj++){
        for(int lk=0;lk<S;lk++) for(int rk=0;rk<S;rk++) tree[id][li][rj][min(S-1,lk+rk+lj)]=max(tree[id][li][rj][min(S-1,lk+rk+lj)],tree[id<<1][li][lj][lk]+tree[id<<1|1][lj][rj][rk]);
    }
}

void update(int l,int r,int id,int tl,int tr,int c,int d){
    if(tr<l || r<tl) return;
    if(tl<=l && r<=tr){
        getnew(id,c,d);
        return;
    }
    pushdown(id);
    int mid=(l+r)>>1;
    update(l,mid,id<<1,tl,tr,c,d);update(mid+1,r,id<<1|1,tl,tr,c,d);
    merge(id);
}

void build(int l,int r,int id){
    if(l==r){
        int d=com[r]-com[l-1];
        for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<S;k++){
            tree[id][i][j][k]=-inf;
            if(i+j+k<=d) tree[id][i][j][k]=0;
        }
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,id<<1);build(mid+1,r,id<<1|1);
    merge(id);
}

void solve(){
    cin >> q >> L;
    for(int i=1;i<=q;i++){
        int t,x,a;cin >> t >> x >> a;
        qq[i]={t,x,a};
        if(t==1){
            com.push_back(x);
            com.push_back(x+1);
        }
        else{
            com.push_back(x-L);
            com.push_back(x+L+1);
        }
    }
    com.push_back(INT_MIN);
    sort(com.begin(),com.end());
    com.erase(unique(com.begin(),com.end()),com.end());
    sz=(int)com.size();com.push_back(INT_MAX);
    build(1,sz,1);

    int sum=0;
    for(int i=1;i<=q;i++){
        auto [t,x,a]=qq[i];
        if(t==1){
            sum+=a;
            int l=get_pos(x),r=get_pos(x+1);
            update(1,sz,1,l,r-1,a,0);
            update(1,sz,1,r,sz,a,a);
        }
        else{
            int l=get_pos(x-L),r=get_pos(x+L+1);
            update(1,sz,1,l,r-1,-a,0);
            update(1,sz,1,r,sz,-a,-a);
        }
        int res=0;
        for(int j=0;j<S;j++) res=max(res,tree[1][0][0][j]);
        cout << sum-res << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 6 ms 7004 KB Output is correct
7 Correct 5 ms 6744 KB Output is correct
8 Correct 4 ms 6744 KB Output is correct
9 Correct 3 ms 6748 KB Output is correct
10 Correct 9 ms 7000 KB Output is correct
11 Correct 8 ms 5208 KB Output is correct
12 Correct 8 ms 4952 KB Output is correct
13 Correct 9 ms 5152 KB Output is correct
14 Correct 9 ms 4956 KB Output is correct
15 Correct 10 ms 7104 KB Output is correct
16 Correct 8 ms 4952 KB Output is correct
17 Correct 9 ms 4956 KB Output is correct
18 Correct 8 ms 4956 KB Output is correct
19 Correct 8 ms 7004 KB Output is correct
20 Correct 8 ms 7004 KB Output is correct
21 Correct 9 ms 4956 KB Output is correct
22 Correct 8 ms 7084 KB Output is correct
23 Correct 9 ms 7004 KB Output is correct
24 Correct 8 ms 5140 KB Output is correct
25 Correct 9 ms 7004 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1607 ms 106552 KB Output is correct
5 Correct 694 ms 59272 KB Output is correct
6 Correct 1905 ms 110048 KB Output is correct
7 Correct 705 ms 59152 KB Output is correct
8 Correct 2407 ms 112604 KB Output is correct
9 Correct 1606 ms 122160 KB Output is correct
10 Correct 2383 ms 121552 KB Output is correct
11 Correct 1519 ms 121808 KB Output is correct
12 Correct 681 ms 61128 KB Output is correct
13 Correct 968 ms 109428 KB Output is correct
14 Correct 1604 ms 118684 KB Output is correct
15 Correct 1652 ms 118640 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 718 ms 56900 KB Output is correct
3 Correct 962 ms 104052 KB Output is correct
4 Correct 1623 ms 109248 KB Output is correct
5 Correct 1615 ms 109456 KB Output is correct
6 Correct 1848 ms 107176 KB Output is correct
7 Correct 122 ms 13784 KB Output is correct
8 Correct 862 ms 95320 KB Output is correct
9 Correct 1409 ms 100124 KB Output is correct
10 Correct 2874 ms 191412 KB Output is correct
11 Correct 3026 ms 202168 KB Output is correct
12 Correct 2861 ms 201836 KB Output is correct
13 Correct 2775 ms 202140 KB Output is correct
14 Correct 2839 ms 202272 KB Output is correct
15 Correct 2753 ms 201772 KB Output is correct
16 Correct 2823 ms 202004 KB Output is correct
17 Correct 3067 ms 201916 KB Output is correct
18 Correct 3248 ms 202040 KB Output is correct
19 Correct 3292 ms 202076 KB Output is correct
20 Correct 3215 ms 202324 KB Output is correct
21 Correct 3265 ms 202044 KB Output is correct
22 Correct 3299 ms 201868 KB Output is correct
23 Correct 3447 ms 201884 KB Output is correct
24 Correct 3123 ms 202052 KB Output is correct
25 Correct 3321 ms 201868 KB Output is correct

Subtask #4
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 6 ms 7004 KB Output is correct
7 Correct 5 ms 6744 KB Output is correct
8 Correct 4 ms 6744 KB Output is correct
9 Correct 3 ms 6748 KB Output is correct
10 Correct 9 ms 7000 KB Output is correct
11 Correct 8 ms 5208 KB Output is correct
12 Correct 8 ms 4952 KB Output is correct
13 Correct 9 ms 5152 KB Output is correct
14 Correct 9 ms 4956 KB Output is correct
15 Correct 10 ms 7104 KB Output is correct
16 Correct 8 ms 4952 KB Output is correct
17 Correct 9 ms 4956 KB Output is correct
18 Correct 8 ms 4956 KB Output is correct
19 Correct 8 ms 7004 KB Output is correct
20 Correct 8 ms 7004 KB Output is correct
21 Correct 9 ms 4956 KB Output is correct
22 Correct 8 ms 7084 KB Output is correct
23 Correct 9 ms 7004 KB Output is correct
24 Correct 8 ms 5140 KB Output is correct
25 Correct 9 ms 7004 KB Output is correct
26 Correct 1 ms 2392 KB Output is correct
27 Correct 1 ms 2396 KB Output is correct
28 Correct 1 ms 2396 KB Output is correct
29 Correct 1607 ms 106552 KB Output is correct
30 Correct 694 ms 59272 KB Output is correct
31 Correct 1905 ms 110048 KB Output is correct
32 Correct 705 ms 59152 KB Output is correct
33 Correct 2407 ms 112604 KB Output is correct
34 Correct 1606 ms 122160 KB Output is correct
35 Correct 2383 ms 121552 KB Output is correct
36 Correct 1519 ms 121808 KB Output is correct
37 Correct 681 ms 61128 KB Output is correct
38 Correct 968 ms 109428 KB Output is correct
39 Correct 1604 ms 118684 KB Output is correct
40 Correct 1652 ms 118640 KB Output is correct
41 Correct 1 ms 2396 KB Output is correct
42 Correct 718 ms 56900 KB Output is correct
43 Correct 962 ms 104052 KB Output is correct
44 Correct 1623 ms 109248 KB Output is correct
45 Correct 1615 ms 109456 KB Output is correct
46 Correct 1848 ms 107176 KB Output is correct
47 Correct 122 ms 13784 KB Output is correct
48 Correct 862 ms 95320 KB Output is correct
49 Correct 1409 ms 100124 KB Output is correct
50 Correct 2874 ms 191412 KB Output is correct
51 Correct 3026 ms 202168 KB Output is correct
52 Correct 2861 ms 201836 KB Output is correct
53 Correct 2775 ms 202140 KB Output is correct
54 Correct 2839 ms 202272 KB Output is correct
55 Correct 2753 ms 201772 KB Output is correct
56 Correct 2823 ms 202004 KB Output is correct
57 Correct 3067 ms 201916 KB Output is correct
58 Correct 3248 ms 202040 KB Output is correct
59 Correct 3292 ms 202076 KB Output is correct
60 Correct 3215 ms 202324 KB Output is correct
61 Correct 3265 ms 202044 KB Output is correct
62 Correct 3299 ms 201868 KB Output is correct
63 Correct 3447 ms 201884 KB Output is correct
64 Correct 3123 ms 202052 KB Output is correct
65 Correct 3321 ms 201868 KB Output is correct
66 Correct 1360 ms 106704 KB Output is correct
67 Correct 1608 ms 112460 KB Output is correct
68 Correct 1928 ms 116696 KB Output is correct
69 Correct 1768 ms 113224 KB Output is correct
70 Correct 2798 ms 204908 KB Output is correct
71 Correct 2825 ms 205188 KB Output is correct
72 Correct 2910 ms 205052 KB Output is correct
73 Correct 2916 ms 204624 KB Output is correct
74 Correct 2959 ms 199060 KB Output is correct
75 Correct 2918 ms 204372 KB Output is correct
76 Correct 2763 ms 204320 KB Output is correct
77 Correct 2677 ms 198980 KB Output is correct
78 Correct 2726 ms 199036 KB Output is correct
79 Correct 2942 ms 205052 KB Output is correct
80 Correct 2680 ms 198924 KB Output is correct
81 Correct 2864 ms 204928 KB Output is correct
82 Correct 2723 ms 198640 KB Output is correct
83 Correct 3276 ms 205440 KB Output is correct
84 Correct 2706 ms 198752 KB Output is correct
85 Correct 3392 ms 205220 KB Output is correct
86 Correct 2765 ms 198760 KB Output is correct
87 Correct 3401 ms 205260 KB Output is correct
88 Correct 2812 ms 198608 KB Output is correct
89 Correct 3183 ms 205216 KB Output is correct