oj.uz

Submission #415740

# Submission time Handle Problem Language Result Execution time Memory
415740 2021-06-01T12:39:56 Z 송준혁(#7513) Road Construction (JOI21_road_construction) C++17
59 / 100
 1266 ms 511644 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define MOD 1000000007
#define INF (1ll<<60)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,int> pli;

int N, K, num;
int T1[250505], T2[250505], Y[250505];
pii P[250505];
vector<pii> C;

struct Node{
	int l, r, p;
	LL v;
} S[10101010];

void upd(int pv, int nw, int s, int e, int t, LL v){
	int m=s+e>>1;
	if (s == e){
		S[nw].p = s, S[nw].v = v;
		return;
	}
	if (t <= m){
		S[nw].l = ++num, S[nw].r = S[pv].r;
		upd(S[pv].l, S[nw].l, s, m, t, v);
	}
	else{
		S[nw].r = ++num, S[nw].l = S[pv].l;
		upd(S[pv].r, S[nw].r, m+1, e, t, v);
	}
	if (S[S[nw].l].v < S[S[nw].r].v) S[nw].v = S[S[nw].l].v, S[nw].p = S[S[nw].l].p;
	else S[nw].v = S[S[nw].r].v, S[nw].p = S[S[nw].r].p;
}

int rmq(int id, int s, int e, int ts, int te){
	if (e < ts || te < s) return 0;
	if (ts <= s && e <= te) return id;
	int m = s+e>>1;
	int r1 = rmq(S[id].l, s, m, ts, te);
	int r2 = rmq(S[id].r, m+1, e, ts, te);
	return (S[r1].v < S[r2].v)?r1:r2;
}

priority_queue<pli> PQ;

int main(){
	S[0].v = INF;
	scanf("%d %d", &N, &K);
	for (int i=1; i<=N; i++){
		scanf("%d %d", &P[i].fi, &P[i].se);
		C.pb(pii(P[i].se, P[i].fi));
	}
	sort(C.begin(), C.end());
	sort(P+1, P+N+1);
	for (int i=1; i<=N; i++){
		Y[i] = lb(C.begin(), C.end(), pii(P[i].se, P[i].fi))-C.begin()+1;
		T1[i] = ++num, upd(T1[i-1], T1[i], 1, N, Y[i], -P[i].fi-P[i].se);
		T2[i] = ++num, upd(T2[i-1], T2[i], 1, N, Y[i], -P[i].fi+P[i].se);
		PQ.push(pli(-P[i].fi-P[i].se - S[rmq(T1[i], 1, N, 1, Y[i]-1)].v, i));
		PQ.push(pli(-P[i].fi+P[i].se - S[rmq(T2[i], 1, N, Y[i]+1, N)].v, -i));
	}
	while (K--){
		LL l;
		int x;
		tie(l, x) = PQ.top(); PQ.pop();
		printf("%lld\n", -l);
		if (x>0){
			int t = rmq(T1[x], 1, N, 1, Y[x]-1);
			int p=T1[x]; T1[x] = ++num;
			upd(p, T1[x], 1, N, S[t].p, INF);
			PQ.push(pli(-P[x].fi-P[x].se - S[rmq(T1[x], 1, N, 1, Y[x]-1)].v, x));
		}
		else{
			x=-x;
			int t = rmq(T2[x], 1, N, Y[x]+1, N);
			int p=T2[x]; T2[x] = ++num;
			upd(p, T2[x], 1, N, S[t].p, INF);
			PQ.push(pli(-P[x].fi+P[x].se - S[rmq(T2[x], 1, N, Y[x]+1, N)].v, -x));
		}
	}
	return 0;
}

Compilation message

road_construction.cpp: In function 'void upd(int, int, int, int, int, LL)':
road_construction.cpp:24:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |  int m=s+e>>1;
      |        ~^~
road_construction.cpp: In function 'int rmq(int, int, int, int, int)':
road_construction.cpp:44:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |  int m = s+e>>1;
      |          ~^~
road_construction.cpp: In function 'int main()':
road_construction.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  scanf("%d %d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%d %d", &P[i].fi, &P[i].se);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 67916 KB Output is correct
2 Correct 373 ms 67824 KB Output is correct
3 Correct 337 ms 65224 KB Output is correct
4 Correct 341 ms 65184 KB Output is correct
5 Correct 366 ms 66696 KB Output is correct
6 Correct 5 ms 1484 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 861 ms 511644 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 957 ms 237604 KB Output is correct
2 Correct 911 ms 242644 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 506 ms 240484 KB Output is correct
5 Correct 679 ms 242904 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 957 ms 237604 KB Output is correct
2 Correct 911 ms 242644 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 506 ms 240484 KB Output is correct
5 Correct 679 ms 242904 KB Output is correct
6 Correct 1056 ms 242644 KB Output is correct
7 Correct 901 ms 242612 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1044 ms 242608 KB Output is correct
11 Correct 484 ms 240572 KB Output is correct
12 Correct 618 ms 242952 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 67916 KB Output is correct
2 Correct 373 ms 67824 KB Output is correct
3 Correct 337 ms 65224 KB Output is correct
4 Correct 341 ms 65184 KB Output is correct
5 Correct 366 ms 66696 KB Output is correct
6 Correct 5 ms 1484 KB Output is correct
7 Correct 1266 ms 197236 KB Output is correct
8 Correct 1227 ms 197264 KB Output is correct
9 Correct 283 ms 65516 KB Output is correct
10 Correct 742 ms 196568 KB Output is correct
11 Correct 859 ms 196372 KB Output is correct
12 Correct 609 ms 197220 KB Output is correct
13 Correct 646 ms 195880 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 67916 KB Output is correct
2 Correct 373 ms 67824 KB Output is correct
3 Correct 337 ms 65224 KB Output is correct
4 Correct 341 ms 65184 KB Output is correct
5 Correct 366 ms 66696 KB Output is correct
6 Correct 5 ms 1484 KB Output is correct
7 Runtime error 861 ms 511644 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -