Submission #289869

# Submission time Handle Problem Language Result Execution time Memory
289869 2020-09-03T07:37:36 Z 송준혁(#5776) None (JOI12_invitation) C++17
0 / 100
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(T[id*2],lz[id]), lz[id*2+1]=max(T[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);
	}
	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 29 ms 38016 KB Output is correct
2 Incorrect 27 ms 38144 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 38144 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 39296 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 39584 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 39680 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 828 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 930 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 793 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 3071 ms 126080 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 144 ms 50676 KB Output is correct
2 Runtime error 859 ms 131072 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -