oj.uz

답안 #708354

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
708354 2023-03-11T15:47:31 Z doowey Ants and Sugar (JOI22_sugar) C++14
22 / 100
 4000 ms 131560 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
const int N = (int)5e5 + 10;
int typ[N];
int X[N];
int A[N];

struct Node{
    ll dp[2][2][3]; // [start][end][x_cnt]
    ll lazy_x;
    ll lazy_both;
};
 
void upd(ll &a, ll b){
    a = max(a, b);
}

Node make_node(){
    Node r;
    for(int i = 0 ; i < 2; i ++ ){
        for(int j = 0; j < 2; j ++ ){
            for(int k = 0 ;k < 3; k ++ ){
                r.dp[i][j][k] = -(ll)1e18;
            }
        }
    }
    r.lazy_x = 0ll;
    r.lazy_both = 0ll;
    return r;
}

const Node D = make_node();
ll mx[3];


Node unite(Node aa, Node bb){
    Node res = aa;
    int cum;
    for(int st = 0 ; st < 2; st ++ ){
        for(int en = 0; en < 2; en ++ ){
            upd(res.dp[st][en][1], aa.dp[st][0][0] + bb.dp[1][en][1]);
            upd(res.dp[st][en][1], aa.dp[st][1][1] + bb.dp[0][en][0]);
            upd(res.dp[st][en][0], bb.dp[st][en][0]);
            for(int pi = st; pi < 3; pi ++ ){
                for(int qi = max(2-pi, en); qi < 3; qi ++ ){
                    upd(res.dp[st][en][2], aa.dp[st][0][pi] + bb.dp[1][en][qi]);
                    upd(res.dp[st][en][2], aa.dp[st][1][pi] + bb.dp[0][en][qi]);
                }
                upd(res.dp[st][en][pi], bb.dp[st][en][pi]);
            }
        }
    }
    return res;
}
 
Node T[N * 4 + 512];
 
void push(int node, int cl, int cr){
    int bonus;
    for(int st = 0; st < 2; st ++ ){
        for(int en = 0; en < 2; en ++ ){
            for(int cc = 0; cc < 3; cc ++ ){
                if(st == en){
                    bonus = st;
                }
                else{
                    bonus = -1;
                }
                if(bonus != -1){
                    if(bonus == 0) T[node].dp[st][en][cc] -= T[node].lazy_both;
                    else T[node].dp[st][en][cc] += T[node].lazy_both;
                }
                T[node].dp[st][en][cc] += cc * 1ll * T[node].lazy_x;
            }
        }
    }
    if(cl != cr){
        T[node * 2].lazy_x += T[node].lazy_x;
        T[node * 2 + 1].lazy_x += T[node].lazy_x;
        T[node * 2].lazy_both += T[node].lazy_both;
        T[node * 2 + 1].lazy_both += T[node].lazy_both;
    }
    T[node].lazy_x = T[node].lazy_both = 0;
}
 
void update(int node, int cl, int cr, int tl, int tr, int Xi, int Yi){
    push(node, cl, cr);
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        if(Xi == Yi){
            T[node].lazy_both = Xi;
        }
        else{
            T[node].lazy_x = Xi;
        }
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2ll;
    update(node * 2, cl, mid, tl, tr, Xi, Yi);
    update(node * 2 + 1, mid + 1, cr, tl, tr, Xi, Yi);
    T[node] = unite(T[node * 2], T[node * 2 + 1]);
}
 
int k;
vector<int> posi;
void perform_update(int tl, int tr, int Xi, int Yi){
    int ii = lower_bound(posi.begin(), posi.end(), tl) - posi.begin();
    int jj = lower_bound(posi.begin(), posi.end(), tr + 1) - posi.begin();
    jj -- ;
    //cout << ii << " " << jj << " | " << Xi << " " << Yi << "\n";
    if(ii <= jj)
        update(1, 0, k - 1, ii, jj, Xi, Yi);
}

void build(int node, int cl, int cr){
    T[node] = D;
    if(cl == cr){
        T[node].dp[0][0][0] = 0;
        T[node].dp[0][1][1] = 0;
        T[node].dp[1][1][1] = 0;
        return;
    }
    int mid = (cl + cr) / 2;
    build(node * 2, cl, mid);
    build(node * 2 + 1, mid + 1, cr);
    T[node] = unite(T[node * 2], T[node * 2 + 1]);
}
 
ll get_max(){
    ll V = 0ll;
    V = max(V, T[1].dp[0][1][1]);
    V = max(V, T[1].dp[0][1][2]);
    return V;
}
 
int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    int q, d;
    cin >> q >> d;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> typ[iq] >> X[iq] >> A[iq];
        posi.push_back(X[iq]);
    }
    sort(posi.begin(), posi.end());
    posi.resize(unique(posi.begin(), posi.end()) - posi.begin());
    k = posi.size();
    
    build(1, 0, k - 1);
    ll ants = 0ll;
    for(int iq = 1; iq <= q; iq ++ ){
        if(typ[iq] == 1){
            perform_update(X[iq] + 1, (int)1e9, A[iq], A[iq]);
            perform_update(X[iq], X[iq], A[iq], 0);
            ants += A[iq];
        }
        else{
            perform_update(X[iq] + d + 1, (int)1e9, -A[iq], -A[iq]);
            perform_update(X[iq] - d, X[iq] + d, -A[iq], 0);
        }
        cout << ants - get_max() << "\n";
 
    }
    return 0;
}

Compilation message

sugar.cpp: In function 'Node unite(Node, Node)':
sugar.cpp:48:9: warning: unused variable 'cum' [-Wunused-variable]
   48 |     int cum;
      |         ^~~

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 9 ms 920 KB Output is correct
7 Correct 9 ms 880 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 14 ms 1400 KB Output is correct
11 Correct 14 ms 1364 KB Output is correct
12 Correct 15 ms 1364 KB Output is correct
13 Correct 17 ms 1388 KB Output is correct
14 Correct 14 ms 1384 KB Output is correct
15 Correct 14 ms 1388 KB Output is correct
16 Correct 14 ms 1324 KB Output is correct
17 Correct 14 ms 1364 KB Output is correct
18 Correct 14 ms 1364 KB Output is correct
19 Correct 14 ms 1364 KB Output is correct
20 Correct 14 ms 1368 KB Output is correct
21 Correct 16 ms 1392 KB Output is correct
22 Correct 14 ms 1368 KB Output is correct
23 Correct 18 ms 1396 KB Output is correct
24 Correct 14 ms 1364 KB Output is correct
25 Correct 11 ms 1364 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2663 ms 69220 KB Output is correct
5 Correct 1510 ms 65548 KB Output is correct
6 Correct 3083 ms 88060 KB Output is correct
7 Correct 1533 ms 65456 KB Output is correct
8 Correct 3984 ms 130656 KB Output is correct
9 Correct 3356 ms 131448 KB Output is correct
10 Correct 3714 ms 131076 KB Output is correct
11 Correct 3343 ms 131560 KB Output is correct
12 Correct 1430 ms 63916 KB Output is correct
13 Correct 2021 ms 123320 KB Output is correct
14 Correct 3401 ms 128132 KB Output is correct
15 Correct 3581 ms 128104 KB Output is correct

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1412 ms 64092 KB Output is correct
3 Correct 1992 ms 123584 KB Output is correct
4 Correct 3349 ms 128384 KB Output is correct
5 Correct 3290 ms 128000 KB Output is correct
6 Correct 3043 ms 117340 KB Output is correct
7 Correct 184 ms 8840 KB Output is correct
8 Correct 1429 ms 63400 KB Output is correct
9 Correct 2174 ms 65808 KB Output is correct
10 Correct 3976 ms 127876 KB Output is correct
11 Execution timed out 4003 ms 127720 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 9 ms 920 KB Output is correct
7 Correct 9 ms 880 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 14 ms 1400 KB Output is correct
11 Correct 14 ms 1364 KB Output is correct
12 Correct 15 ms 1364 KB Output is correct
13 Correct 17 ms 1388 KB Output is correct
14 Correct 14 ms 1384 KB Output is correct
15 Correct 14 ms 1388 KB Output is correct
16 Correct 14 ms 1324 KB Output is correct
17 Correct 14 ms 1364 KB Output is correct
18 Correct 14 ms 1364 KB Output is correct
19 Correct 14 ms 1364 KB Output is correct
20 Correct 14 ms 1368 KB Output is correct
21 Correct 16 ms 1392 KB Output is correct
22 Correct 14 ms 1368 KB Output is correct
23 Correct 18 ms 1396 KB Output is correct
24 Correct 14 ms 1364 KB Output is correct
25 Correct 11 ms 1364 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 324 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 2663 ms 69220 KB Output is correct
30 Correct 1510 ms 65548 KB Output is correct
31 Correct 3083 ms 88060 KB Output is correct
32 Correct 1533 ms 65456 KB Output is correct
33 Correct 3984 ms 130656 KB Output is correct
34 Correct 3356 ms 131448 KB Output is correct
35 Correct 3714 ms 131076 KB Output is correct
36 Correct 3343 ms 131560 KB Output is correct
37 Correct 1430 ms 63916 KB Output is correct
38 Correct 2021 ms 123320 KB Output is correct
39 Correct 3401 ms 128132 KB Output is correct
40 Correct 3581 ms 128104 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 1412 ms 64092 KB Output is correct
43 Correct 1992 ms 123584 KB Output is correct
44 Correct 3349 ms 128384 KB Output is correct
45 Correct 3290 ms 128000 KB Output is correct
46 Correct 3043 ms 117340 KB Output is correct
47 Correct 184 ms 8840 KB Output is correct
48 Correct 1429 ms 63400 KB Output is correct
49 Correct 2174 ms 65808 KB Output is correct
50 Correct 3976 ms 127876 KB Output is correct
51 Execution timed out 4003 ms 127720 KB Time limit exceeded
52 Halted 0 ms 0 KB -