# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
123278 |
2019-07-01T05:21:45 Z |
임유진(#3021) |
Two Antennas (JOI19_antennas) |
C++14 |
|
1255 ms |
12620 KB |
#include <stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define MAXN 200005
#define fi first
#define se second
typedef pair<int, int> pii;
const int INF = 1e9 + 5;
int H[MAXN], A[MAXN], B[MAXN], L[MAXN], R[MAXN];
int cseg[4*MAXN];
int mnseg[4*MAXN], mxseg[4*MAXN];
void updseg(int idx, int l, int r, int x, int y) {
if(l == r) {
mnseg[idx] = mxseg[idx] = y;
return;
}
int m = (l + r) / 2;
if(x <= m) updseg(idx * 2, l, m, x, y);
else updseg(idx * 2 + 1, m + 1, r, x, y);
mnseg[idx] = min(mnseg[idx * 2], mnseg[idx * 2 + 1]);
mxseg[idx] = max(mxseg[idx * 2], mxseg[idx * 2 + 1]);
}
int gmax(int idx, int l, int r, int x, int y) {
//printf("gmax(idx=%d, l=%d, r=%d, x=%d, y=%d)\n", idx, l, r, x, y);
if(x <= l && r <= y) return mxseg[idx];
if(r < x || y < l) return -INF;
int m = (l + r) / 2;
return max(gmax(idx * 2, l, m, x, y), gmax(idx * 2 + 1, m + 1, r, x, y));
}
int gmin(int idx, int l, int r, int x, int y) {
if(x <= l && r <= y) return mnseg[idx];
if(r < x || y < l) return INF;
int m = (l + r) / 2;
return min(gmin(idx * 2, l, m, x, y), gmin(idx * 2 + 1, m + 1, r, x, y));
}
void rmseg(int idx, int l, int r, int x) {
//printf("rmseg(idx = %d, l = %d, r = %d, x = %d)\n", idx, l, r, x);
if(l == r) {
mnseg[idx] = INF;
mxseg[idx] = -INF;
return;
}
int m = (l + r) / 2;
if(idx <= m) rmseg(idx * 2, l, m, x);
else rmseg(idx * 2 + 1, m + 1, r, x);
mnseg[idx] = min(mnseg[idx * 2], mnseg[idx * 2 + 1]);
mxseg[idx] = max(mxseg[idx * 2], mxseg[idx * 2 + 1]);
}
int qtime(const pii a) {
if(a.se == 1) return a.fi + A[a.fi];
else if(a.se == 2) return a.fi;
else return a.fi + B[a.fi];
}
bool cmp(const pii a, const pii b) {
int ta = qtime(a), tb = qtime(b);
return ta != tb ? ta < tb : a.se < b.se;
}
int maxcost(int l, int m, int r) {
//printf("maxcost(l = %d, m = %d, r = %d)\n", l, m, r);
vector<pii> query;
int ans = -1;
for(int i = l; i <= m; i++) {
query.push_back(make_pair(i, 1));
query.push_back(make_pair(i, 3));
}
for(int i = m + 1; i <= r; i++)
query.push_back(make_pair(i, 2));
sort(query.begin(), query.end(), cmp);
for(int i = 1; i < 4 * (m-l+1); i++) {
mnseg[i] = INF;
mxseg[i] = -INF;
}
for(auto a : query) {
//printf("(%d, %d)\n", a.fi, a.se);
if(a.se == 1) updseg(1, l, m, a.fi, H[a.fi]);
else if(a.se== 2) {
if(a.fi - B[a.fi] <= m && a.fi - A[a.fi] >= l) {
//printf("%d ", ans);
ans = max(ans, gmax(1, l, m, max(l, a.fi- B[a.fi]), min(m, a.fi - A[a.fi])) - H[a.fi]);
//printf("%d ", ans);
ans = max(ans, H[a.fi] - gmin(1, l, m, max(l, a.fi - B[a.fi]), min(m, a.fi - A[a.fi])));
//printf("%d\n", ans);
}
}
else rmseg(1, l, m, a.fi);
}
//printf("maxcost(l=%d, m=%d, r=%d) = %d\n", l, m, r, ans);
return ans;
}
void mkcseg(int idx, int l, int r) {
//printf("mkcseg(idx = %d, l = %d, r = %d)\n", idx, l, r);
if(l == r) {
cseg[idx] = -1;
return;
}
int m = (l + r) / 2;
mkcseg(idx * 2, l, m);
mkcseg(idx * 2 + 1, m + 1, r);
cseg[idx] = max(max(cseg[idx*2], cseg[idx*2+1]), maxcost(l, m, r));
//printf("cseg[%d] = %d\n", idx, cseg[idx]);
}
int gcseg(int idx, int l, int r, int x, int y) {
//printf("gcseg(idx = %d, l = %d, r = %d, x = %d, y = %d)\n", idx, l, r, x, y);
if(x <= l && r <= y) return cseg[idx];
int m = (l + r) / 2;
if(y <= m) return gcseg(idx * 2, l, m, x, y);
if(x > m) return gcseg(idx * 2 + 1, m + 1, r, x, y);
return max(max(gcseg(idx * 2, l, m, x, y), gcseg(idx * 2 + 1, m + 1, r, x, y)), maxcost(max(l, x), m, min(r, y)));
}
int main() {
int N, Q;
scanf("%d", &N);
for(int i = 0; i < N; i++) scanf("%d%d%d", H+i, A+i, B+i);
scanf("%d", &Q);
for(int i = 0; i < Q; i++) scanf("%d%d", L+i, R+i);
mkcseg(1, 0, N-1);
for(int i = 0; i < Q; i++) printf("%d\n", gcseg(1, 0, N-1, L[i]-1, R[i]-1));
return 0;
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:131:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
antennas.cpp:132:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 0; i < N; i++) scanf("%d%d%d", H+i, A+i, B+i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
~~~~~^~~~~~~~~~
antennas.cpp:134:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 0; i < Q; i++) scanf("%d%d", L+i, R+i);
~~~~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1109 ms |
12112 KB |
Output is correct |
2 |
Correct |
1249 ms |
12460 KB |
Output is correct |
3 |
Correct |
834 ms |
8212 KB |
Output is correct |
4 |
Correct |
1255 ms |
12532 KB |
Output is correct |
5 |
Correct |
521 ms |
6356 KB |
Output is correct |
6 |
Correct |
1252 ms |
12620 KB |
Output is correct |
7 |
Incorrect |
1057 ms |
9412 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |