| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 289919 |
2020-09-03T08:39:07 Z |
송준혁(#5776) |
None (JOI12_invitation) |
C++17 |
|
3000 ms |
131076 KB |
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
int N, M, Q, S, P;
pii X[101010], Y[101010];
int T[1606060], lz[1606060], cnt[1606060], W[101010];
bool chk[404040];
LL ans;
vector<LL> C;
struct qry{int s, e, w;};
vector<qry> V[1606060];
void updg(int id, int s, int e, int ts, int te, qry v){
if (e < ts || te < s) return;
if (ts <= s && e <= te){V[id].pb(v); return;}
int m=s+e>>1;
updg(id*2, s, m, ts, te, v);
updg(id*2+1, m+1, e, ts, te, v);
}
void busy(int id){
if (!lz[id]) return;
if (cnt[id*2]) T[id*2]=max(T[id*2],lz[id]), T[id*2+1]=max(T[id*2+1],lz[id]);
if (cnt[id*2+1]) lz[id*2]=max(lz[id*2],lz[id]), lz[id*2+1]=max(lz[id*2+1],lz[id]);
lz[id] = 0;
}
void updh(int id, int s, int e, int ts, int te, int v){
if (e < ts || te < s || !cnt[id]) return;
if (ts <= s && e <= te){T[id]=max(T[id],v), lz[id]=max(lz[id],v); return;}
busy(id);
int m=s+e>>1;
updh(id*2, s, m, ts, te, v);
updh(id*2+1, m+1, e, ts, te, v);
T[id] = max(T[id*2], T[id*2+1]);
}
void updc(int id, int s, int e, int t){
if (e < t || t < s) return;
cnt[id]--;
if (!cnt[id]) T[id]=0;
if (s == e) return;
busy(id);
int m=s+e>>1;
updc(id*2, s, m, t);
updc(id*2+1, m+1, e, t);
if (cnt[id]) T[id] = max(T[id*2], T[id*2+1]);
}
int inv(int id, int s, int e){
if (s == e) return s;
busy(id);
int m=s+e>>1;
if (T[id*2] >= T[id*2+1]) return inv(id*2, s, m);
return inv(id*2+1, m+1, e);
}
void app(int id, int s, int e, int t){
if (e < t || t < s) return;
for (qry p : V[id]) updh(1, 1, P, p.s, p.e, p.w);
V[id].clear();
if (s == e) return;
int m=s+e>>1;
app(id*2, s, m, t);
app(id*2+1, m+1, e, t);
}
void init(int id, int s, int e){
cnt[id] = (e-s+1)*2;
if (s == e) return;
int m=s+e>>1;
init(id*2, s, m), init(id*2+1, m+1, e);
}
int main(){
scanf("%d %d %d", &N, &M, &S);
scanf("%d", &Q);
for (int i=1; i<=Q; i++){
scanf("%d %d %d %d %d", &X[i].fi, &X[i].se, &Y[i].fi, &Y[i].se, &W[i]);
Y[i].fi += N, Y[i].se += N;
C.pb(X[i].fi-1), C.pb(X[i].se);
C.pb(Y[i].fi-1), C.pb(Y[i].se);
}
C.pb(N);
sort(C.begin(), C.end());
C.erase(unique(C.begin(), C.end()), C.end());
P = C.size()-1;
if (C[0] || C.back() != N+M) return !printf("-1\n");
for (int i=1; i<=Q; i++){
X[i].fi = lower_bound(C.begin(), C.end(), X[i].fi)-C.begin();
X[i].se = lower_bound(C.begin(), C.end(), X[i].se)-C.begin();
Y[i].fi = lower_bound(C.begin(), C.end(), Y[i].fi)-C.begin();
Y[i].se = lower_bound(C.begin(), C.end(), Y[i].se)-C.begin();
updg(1, 1, P, X[i].fi, X[i].se, (qry){X[i].fi, X[i].se, W[i]});
updg(1, 1, P, X[i].fi, X[i].se, (qry){Y[i].fi, Y[i].se, W[i]});
updg(1, 1, P, Y[i].fi, Y[i].se, (qry){X[i].fi, X[i].se, W[i]});
updg(1, 1, P, Y[i].fi, Y[i].se, (qry){Y[i].fi, Y[i].se, W[i]});
}
init(1, 1, P);
S = lower_bound(C.begin(), C.end(), S)-C.begin();
updc(1, 1, P, S);
app(1, 1, P, S);
chk[S] = true;
while (T[1]){
S = inv(1, 1, P);
if (chk[S]) ans += (C[S]-C[S-1]-1)*T[1];
else ans += T[1];
chk[S] = true;
updc(1, 1, P, S);
app(1, 1, P, S);
}
if (cnt[1]) puts("-1");
else printf("%lld\n", ans);
return 0;
}
Compilation message
invitation.cpp: In function 'void updg(int, int, int, int, int, qry)':
invitation.cpp:22:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | int m=s+e>>1;
| ~^~
invitation.cpp: In function 'void updh(int, int, int, int, int, int)':
invitation.cpp:38:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int m=s+e>>1;
| ~^~
invitation.cpp: In function 'void updc(int, int, int, int)':
invitation.cpp:50:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
50 | int m=s+e>>1;
| ~^~
invitation.cpp: In function 'int inv(int, int, int)':
invitation.cpp:59:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
59 | int m=s+e>>1;
| ~^~
invitation.cpp: In function 'void app(int, int, int, int)':
invitation.cpp:69:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | int m=s+e>>1;
| ~^~
invitation.cpp: In function 'void init(int, int, int)':
invitation.cpp:77:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
77 | int m=s+e>>1;
| ~^~
invitation.cpp: In function 'int main()':
invitation.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
82 | scanf("%d %d %d", &N, &M, &S);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
invitation.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
83 | scanf("%d", &Q);
| ~~~~~^~~~~~~~~~
invitation.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
85 | scanf("%d %d %d %d %d", &X[i].fi, &X[i].se, &Y[i].fi, &Y[i].se, &W[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
38008 KB |
Output is correct |
| 2 |
Correct |
29 ms |
38144 KB |
Output is correct |
| 3 |
Correct |
25 ms |
38144 KB |
Output is correct |
| 4 |
Correct |
25 ms |
38144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
38144 KB |
Output is correct |
| 2 |
Correct |
25 ms |
38144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
39264 KB |
Output is correct |
| 2 |
Correct |
30 ms |
38656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
39672 KB |
Output is correct |
| 2 |
Correct |
69 ms |
39552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
39684 KB |
Output is correct |
| 2 |
Correct |
72 ms |
39564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
740 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
838 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
723 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3096 ms |
126264 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
135 ms |
50652 KB |
Output is correct |
| 2 |
Runtime error |
805 ms |
131076 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
