티스토리 뷰

알고리즘 관련/BOJ

BOJ)10277 JuQueen

JASON 자손9319 2017. 1. 15. 17:45

문제: icpc.me/10277


C개의 코어가 있을 때 쿼리를 받아 3종류의 연산을 처리해주면 되는 문제이다.


단 코어의 하한선은 0이고 상한선은 N으로 입력으로 주어진다.


쿼리는 다음과 같다 


change X S    코어X를 S만큼 증가시켜라

groupchange A B S    코어 A부터 코어B까지 전부 S만큼 증가시켜라

state X  코어X의 값을 출력하라


단, 코어를 증가시키다가 상한이나 하한에 다다를시 증가를 멈춘다.


change나 groupchange 같은 경우 증가혹은 감소시킨 계수를 출력해야 하는데 우리는 코어를 증가시키다 상한이나 하한에 도달하는 경우를 판단해야한다.


따라서 우리는 구간에 대한 최댓값 최솟값을 세그먼트 트리로 관리하여 구간을 증가 시킬 시 상한혹은 하한에 도달하는지 여부를 판단하여 상한 혹은 하한까지만 증가혹은 감소 시킬 수 있다.


이때 우리는 구간에 대한 갱신연산이 있으므로 구간에 대한 증가연산은 lazy propagation 기법을 사용하여 시간을 줄여주어 TLE를 피할 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <iostream>
#define MAX_C 4587520
#define INF 987654321
using namespace std;
int c, n, o, minseg[* MAX_C], maxseg[* MAX_C], minlazy[* MAX_C], maxlazy[* MAX_C], x, y, z;
void u_maxlazy(int node, int x, int y) {
    if (!maxlazy[node])
        return;
    maxseg[node] += maxlazy[node];
    if (x != y) {
        maxlazy[node * 2+= maxlazy[node];
        maxlazy[node * + 1+= maxlazy[node];
    }
    maxlazy[node] = 0;
}
void u_minlazy(int node, int x, int y) {
    if (!minlazy[node])
        return;
    minseg[node] += minlazy[node];
    if (x != y) {
        minlazy[node * 2+= minlazy[node];
        minlazy[node * + 1+= minlazy[node];
    }
    minlazy[node] = 0;
}
void max_update(int lo, int hi, int val, int node, int x, int y) {
    u_maxlazy(node, x, y);
    if (y < lo || hi < x)
        return;
    if (lo <= x&&<= hi) {
        maxlazy[node] += val;
        u_maxlazy(node, x, y);
        return;
    }
    int mid = (x + y) >> 1;
    max_update(lo, hi, val, node * 2, x, mid);
    max_update(lo, hi, val, node * + 1, mid + 1, y);
    maxseg[node] = max(maxseg[node * 2], maxseg[node * + 1]);
}
void min_update(int lo, int hi, int val, int node, int x, int y) {
    u_minlazy(node, x, y);
    if (y < lo || hi < x)
        return;
    if (lo <= x&&<= hi) {
        minlazy[node] += val;
        u_minlazy(node, x, y);
        return;
    }
    int mid = (x + y) >> 1;
    min_update(lo, hi, val, node * 2, x, mid);
    min_update(lo, hi, val, node * + 1, mid + 1, y);
    minseg[node] = min(minseg[node * 2], minseg[node * + 1]);
}
int maxquery(int lo, int hi, int node, int x, int y) {
    u_maxlazy(node, x, y);
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&<= hi)
        return maxseg[node];
    int mid = (x + y) >> 1;
    return max(maxquery(lo, hi, node * 2, x, mid), maxquery(lo, hi, node * + 1, mid + 1, y));
}
int minquery(int lo, int hi, int node, int x, int y) {
    u_minlazy(node, x, y);
    if (y < lo || hi < x)
        return INF;
    if (lo <= x&&<= hi)
        return minseg[node];
    int mid = (x + y) >> 1;
    return min(minquery(lo, hi, node * 2, x, mid), minquery(lo, hi, node * + 1, mid + 1, y));
}
int main() {
    scanf("%d%d%d"&c, &n, &o);
    for (int i = 0; i < o;i++) {
        string a;
        cin >> a;
        int res;
        if (a == "state") {
            scanf("%d"&x);
            res = maxquery(x, x, 10, c - 1);
        }
        else if (a == "change") {
            scanf("%d%d"&x, &y);
            int v = maxquery(x, x, 10, c - 1);
            if (v + y > n) {
                max_update(x, x, n - v, 10, c - 1);
                min_update(x, x, n - v, 10, c - 1);
                res = n - v;
            }
            else if (v + y < 0) {
                max_update(x, x, -v, 10, c - 1);
                min_update(x, x, -v, 10, c - 1);
                res = -v;
            }
            else {
                max_update(x, x, y, 10, c - 1);
                min_update(x, x, y, 10, c - 1);
                res = y;
            }
        }
        else {
            scanf("%d%d%d"&x, &y, &z);
            if (z > 0) {
                int v = maxquery(x, y, 10, c - 1);
                if (v + z > n) {
                    max_update(x, y, n - v, 10, c - 1);
                    min_update(x, y, n - v, 10, c - 1);
                    res = n - v;
                }
                else {
                    max_update(x, y, z, 10, c - 1);
                    min_update(x, y, z, 10, c - 1);
                    res = z;
                }
            }
            else {
                int v = minquery(x, y, 10, c - 1);
                if (v + z < 0) {
                    max_update(x, y, -v, 10, c - 1);
                    min_update(x, y, -v, 10, c - 1);
                    res = -v;
                }
                else {
                    max_update(x, y, z, 10, c - 1);
                    min_update(x, y, z, 10, c - 1);
                    res = z;
                }
            }
        }
        printf("%d\n", res);
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)3758 KCPC  (0) 2017.01.15
BOJ)8983 사냥꾼  (0) 2017.01.15
BOJ)10277 JuQueen  (0) 2017.01.15
BOJ)2877 4와 7  (0) 2017.01.15
BOJ)2775 부녀회장이 될테야  (0) 2017.01.15
BOJ)5480 전함  (0) 2017.01.14
댓글
댓글쓰기 폼