| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 260970 |
2020-08-11T08:55:19 Z |
송준혁(#5049) |
Sweeping (JOI20_sweeping) |
C++17 |
|
1795 ms |
2097156 KB |
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define Mup(a,x) a=max(a, x)
#define mup(a,x) a=min(a, x)
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define INF (1ll<<60)
#define MOD 1'000'000'007
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
int L, N, M, Q;
int S[1505050], Q1[1010101], Q2[1010101];
int X[1505050], Y[1505050], A[1010101];
vector<int> T[4040404];
void build(int id, int s, int e){
if (s == e){
T[id].pb(A[s]);
return;
}
int m=s+e>>1;
build(id*2, s, m), build(id*2+1, m+1, e);
for (int x : T[id*2]) T[id].pb(x);
for (int x : T[id*2+1]) T[id].pb(x);
inplace_merge(T[id].begin(), T[id].begin()+T[id*2].size(), T[id].end());
}
int query(int id, int s, int e, int ts, int te, int k){
if (e < ts || te < s) return 0;
if (ts <= s && e <= te){
auto it = lower_bound(T[id].begin(), T[id].end(), k);
if (it == T[id].end()) return 0;
return L - *it;
}
int m=s+e>>1;
return max(query(id*2, s, m, ts, te, k), query(id*2+1, m+1, e, ts, te, k));
}
int main(){
scanf("%d %d %d", &L, &N, &Q);
for (int i=1; i<=N; i++) scanf("%d %d", &X[i], &Y[i]);
for (int i=1; i<=Q; i++){
int x, y;
scanf("%d", &x);
if (x == 1){
scanf("%d", &Q1[i]);
Q2[i] = M;
}
else if (x == 2){
M++;
scanf("%d", &A[M]);
Q2[i] = M;
}
else{
N++;
scanf("%d %d", &X[N], &Y[N]);
S[N] = M;
}
}
build(1, 1, M);
for (int i=1; i<=Q; i++){
if (Q1[i] == 0) continue;
printf("%d %d\n", max(X[Q1[i]], query(1, 1, M, S[Q1[i]]+1, Q2[i], Y[Q1[i]])), Y[Q1[i]]);
}
return 0;
}
Compilation message
sweeping.cpp: In function 'void build(int, int, int)':
sweeping.cpp:25:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=s+e>>1;
~^~
sweeping.cpp: In function 'int query(int, int, int, int, int, int)':
sweeping.cpp:39:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=s+e>>1;
~^~
sweeping.cpp: In function 'int main()':
sweeping.cpp:47:10: warning: unused variable 'y' [-Wunused-variable]
int x, y;
^
sweeping.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &L, &N, &Q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:45:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i=1; i<=N; i++) scanf("%d %d", &X[i], &Y[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
sweeping.cpp:50:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q1[i]);
~~~~~^~~~~~~~~~~~~~
sweeping.cpp:55:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &A[M]);
~~~~~^~~~~~~~~~~~~
sweeping.cpp:60:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &X[N], &Y[N]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1115 ms |
2097156 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1724 ms |
177160 KB |
Output is correct |
| 2 |
Correct |
1711 ms |
177192 KB |
Output is correct |
| 3 |
Correct |
1681 ms |
176992 KB |
Output is correct |
| 4 |
Correct |
1457 ms |
183612 KB |
Output is correct |
| 5 |
Correct |
1432 ms |
176756 KB |
Output is correct |
| 6 |
Correct |
1159 ms |
174624 KB |
Output is correct |
| 7 |
Correct |
1795 ms |
176980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1442 ms |
183336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1442 ms |
183336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1115 ms |
2097156 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
