oj.uz

Submission #26180

# Submission time Handle Problem Language Result Execution time Memory
26180 2017-06-28T08:33:12 Z 김현수(#1096) Abduction 2 (JOI17_abduction2) C++11
13 / 100
 3099 ms 524288 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef tuple<ll,ll,ll> tp;
const ll N = 100005, L = 17, inf = 1e18;

ll h, w, q, a[N], inv[N], prv[L][N], nxt[L][N];
bool vis[N];

priority_queue<tp> pq[N];
vector<pll> ord, st;

ll getprv (ll P, ll V) {
	if(a[P] > V) {
		for(ll i=P-1;i>=1;i--) {
			if(a[i] > V) return i;
		}
		return 0;
	}
	ll I = P;
	for(ll i=L;i--;) {
		if(a[prv[i][I]] <= V) I = prv[i][I];
	}
	return prv[0][I];
}

ll getnxt (ll P, ll V) {
	if(a[P] > V) {
		for(ll i=P+1;i<=h+w;i++) {
			if(a[i] > V) return i;
		}
		return 0;
	}
	ll I = P;
	for(ll i=L;i--;) {
		if(a[nxt[i][I]] <= V) I = nxt[i][I];
	}
	return nxt[0][I];
}

void solve () {
	ll P, Q, R = 0;
	scanf("%lld%lld",&P,&Q);
	Q += h;
	pq[inv[P]].push(tp(0, P, Q));
	pq[inv[Q]].push(tp(0, Q, P));
	for(ll i=1;i<=h+w;i++) vis[i] = 0;
	for(ll i=1;i<=h+w;i++) while(!pq[i].empty()) {
		ll A, B, C; tie(A, B, C) = pq[i].top(); pq[i].pop();
		if(vis[C] == i) continue;
		vis[C] = i;
		ll X = getprv(C, a[B]), Y = getnxt(C, a[B]);
		if(X && (X<=h)==(C<=h)) pq[inv[X]].push(tp(A+C-X, X, B));
		else R = max(R, A + C - (C<=h?1:h+1));
		if(Y && (Y<=h)==(C<=h)) pq[inv[Y]].push(tp(A+Y-C, Y, B));
		else R = max(R, A + (C<=h?h:h+w) - C);
	}
	printf("%lld\n",R);
}

int main()
{
	scanf("%lld%lld%lld",&h,&w,&q);
	ord.push_back({0, 0});
	for(ll i=1;i<=h+w;i++) {
		scanf("%lld",&a[i]);
		ord.push_back({a[i], i});
	}
	sort(ord.begin(), ord.end());
	for(ll i=1;i<=h+w;i++) {
		inv[ord[i].Y] = i;
	}
	st.push_back({inf, 0});
	for(ll i=1;i<=h+w;i++) {
		while(st.back().X <= a[i]) st.pop_back();
		prv[0][i] = st.back().Y;
		st.push_back({a[i], i});
	}
	st.clear();
	st.push_back({inf, 0});
	for(ll i=h+w;i>=1;i--) {
		while(st.back().X <= a[i]) st.pop_back();
		nxt[0][i] = st.back().Y;
		st.push_back({a[i], i});
	}
	a[0] = inf;
	for(ll k=1;k<L;k++) for(ll i=1;i<=h+w;i++) {
		nxt[k][i] = nxt[k-1][nxt[k-1][i]];
		prv[k][i] = prv[k-1][prv[k-1][i]];
	}
	while(q--) solve();
}

Compilation message

abduction2.cpp: In function 'void solve()':
abduction2.cpp:46:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&P,&Q);
                         ^
abduction2.cpp: In function 'int main()':
abduction2.cpp:66:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&h,&w,&q);
                                ^
abduction2.cpp:69:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
                      ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33372 KB Output is correct
2 Correct 0 ms 33372 KB Output is correct
3 Correct 0 ms 33372 KB Output is correct
4 Correct 3 ms 33372 KB Output is correct
5 Correct 0 ms 33372 KB Output is correct
6 Correct 0 ms 33372 KB Output is correct
7 Correct 0 ms 33372 KB Output is correct
8 Correct 0 ms 33372 KB Output is correct
9 Correct 0 ms 33372 KB Output is correct
10 Correct 3 ms 33372 KB Output is correct
11 Correct 0 ms 33372 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33372 KB Output is correct
2 Correct 0 ms 33372 KB Output is correct
3 Correct 0 ms 33372 KB Output is correct
4 Correct 3 ms 33372 KB Output is correct
5 Correct 0 ms 33372 KB Output is correct
6 Correct 0 ms 33372 KB Output is correct
7 Correct 0 ms 33372 KB Output is correct
8 Correct 0 ms 33372 KB Output is correct
9 Correct 0 ms 33372 KB Output is correct
10 Correct 3 ms 33372 KB Output is correct
11 Correct 0 ms 33372 KB Output is correct
12 Correct 3 ms 33512 KB Output is correct
13 Correct 3 ms 33512 KB Output is correct
14 Correct 6 ms 33512 KB Output is correct
15 Correct 3 ms 33512 KB Output is correct
16 Correct 0 ms 33512 KB Output is correct
17 Correct 3 ms 33512 KB Output is correct
18 Correct 0 ms 33512 KB Output is correct
19 Memory limit exceeded 3099 ms 524288 KB Memory limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33372 KB Output is correct
2 Correct 0 ms 33372 KB Output is correct
3 Correct 0 ms 33372 KB Output is correct
4 Correct 3 ms 33372 KB Output is correct
5 Correct 0 ms 33372 KB Output is correct
6 Correct 0 ms 33372 KB Output is correct
7 Correct 0 ms 33372 KB Output is correct
8 Correct 0 ms 33372 KB Output is correct
9 Correct 0 ms 33372 KB Output is correct
10 Correct 3 ms 33372 KB Output is correct
11 Correct 0 ms 33372 KB Output is correct
12 Correct 3 ms 33512 KB Output is correct
13 Correct 3 ms 33512 KB Output is correct
14 Correct 6 ms 33512 KB Output is correct
15 Correct 3 ms 33512 KB Output is correct
16 Correct 0 ms 33512 KB Output is correct
17 Correct 3 ms 33512 KB Output is correct
18 Correct 0 ms 33512 KB Output is correct
19 Memory limit exceeded 3099 ms 524288 KB Memory limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 36168 KB Output is correct
2 Correct 49 ms 34568 KB Output is correct
3 Correct 66 ms 36880 KB Output is correct
4 Correct 69 ms 36728 KB Output is correct
5 Correct 89 ms 36492 KB Output is correct
6 Correct 56 ms 33644 KB Output is correct
7 Correct 56 ms 33644 KB Output is correct
8 Memory limit exceeded 2789 ms 524288 KB Memory limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33372 KB Output is correct
2 Correct 0 ms 33372 KB Output is correct
3 Correct 0 ms 33372 KB Output is correct
4 Correct 3 ms 33372 KB Output is correct
5 Correct 0 ms 33372 KB Output is correct
6 Correct 0 ms 33372 KB Output is correct
7 Correct 0 ms 33372 KB Output is correct
8 Correct 0 ms 33372 KB Output is correct
9 Correct 0 ms 33372 KB Output is correct
10 Correct 3 ms 33372 KB Output is correct
11 Correct 0 ms 33372 KB Output is correct
12 Correct 3 ms 33512 KB Output is correct
13 Correct 3 ms 33512 KB Output is correct
14 Correct 6 ms 33512 KB Output is correct
15 Correct 3 ms 33512 KB Output is correct
16 Correct 0 ms 33512 KB Output is correct
17 Correct 3 ms 33512 KB Output is correct
18 Correct 0 ms 33512 KB Output is correct
19 Memory limit exceeded 3099 ms 524288 KB Memory limit exceeded
20 Halted 0 ms 0 KB -