oj.uz

답안 #860760

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
860760 2023-10-14T07:00:01 Z browntoad Two Antennas (JOI19_antennas) C++14
13 / 100
 414 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int, int>
#define ppi pair<pii, int>
#define pip pair<int, pii>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define SZ(x) (int)((x).size())

const ll maxn = 2e5+5;
const ll inf = (1ll<<60);
const ll mod = 1e9+7;

vector<int> seg(4*maxn);

int query(int l, int r, int nl, int nr, int x){
	if (l > nr || r < nl) return -1;
	if (l <= nl && nr <= r) return seg[x];
	int mid = (nl+nr)>>1;
	return max(query(l, r, nl, mid, x+x), query(l, r, mid+1, nr, x+x+1));
}
void modify(int l, int r, int p, int v, int x){
	if (l == r){
		seg[x] = max(seg[x], v);
		return;
	}
	int mid = (l+r)>>1;
	if (l <= p && p <= mid){
		modify(l, mid, p, v, x+x);
	}
	else modify(mid+1, r, p, v, x+x+1);
	seg[x] = max(seg[x+x], seg[x+x+1]);
}

vector<int> ans(maxn);
int n, q;
vector<pip> in;
vector<pip> md, qu;
bool cmp(pip a, pip b){
	return a.s.s < b.s.s;
}
signed main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	fill(ALL(seg), -1);
	cin>>n;
	in.pb({0, {0, 0}});
	REP1(i, n){
		int h, a, b; cin>>h>>a>>b;
		in.pb({h, {a, b}});
		for (int j = i-a; j >= 1; j--){
			if (i-j > b) break;
			if (in[j].s.f <= i-j && in[j].s.s >= i-j){
				md.pb({abs(in[j].f-in[i].f), {j, i}});
			}
		}
	}
	cin>>q;
	REP(i, q){
		int l, r; cin>>l>>r;
		qu.pb({i, {l, r}});
	}

	sort(ALL(md), cmp);
	sort(ALL(qu), cmp);
	int pa = 0;
	REP(i, q){
		while(pa < SZ(md) && md[pa].s.s <= qu[i].s.s){
			modify(1, n, md[pa].s.f, md[pa].f, 1);
			pa++;
		}
		ans[qu[i].f] = query(qu[i].s.f, qu[i].s.s, 1, n, 1);
	}
	REP(i, q) cout<<ans[i]<<endl;
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 4 ms 8500 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 3 ms 8284 KB Output is correct
7 Correct 3 ms 8284 KB Output is correct
8 Correct 3 ms 8284 KB Output is correct
9 Correct 3 ms 8280 KB Output is correct
10 Correct 3 ms 8284 KB Output is correct
11 Correct 3 ms 8284 KB Output is correct
12 Correct 3 ms 8336 KB Output is correct
13 Correct 4 ms 8536 KB Output is correct
14 Correct 2 ms 8284 KB Output is correct
15 Correct 3 ms 8340 KB Output is correct
16 Correct 3 ms 8284 KB Output is correct
17 Correct 3 ms 8252 KB Output is correct
18 Correct 3 ms 8284 KB Output is correct
19 Correct 2 ms 8284 KB Output is correct
20 Correct 3 ms 8284 KB Output is correct
21 Correct 3 ms 8284 KB Output is correct
22 Correct 3 ms 8284 KB Output is correct
23 Correct 3 ms 8284 KB Output is correct
24 Correct 3 ms 8284 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 4 ms 8500 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 3 ms 8284 KB Output is correct
7 Correct 3 ms 8284 KB Output is correct
8 Correct 3 ms 8284 KB Output is correct
9 Correct 3 ms 8280 KB Output is correct
10 Correct 3 ms 8284 KB Output is correct
11 Correct 3 ms 8284 KB Output is correct
12 Correct 3 ms 8336 KB Output is correct
13 Correct 4 ms 8536 KB Output is correct
14 Correct 2 ms 8284 KB Output is correct
15 Correct 3 ms 8340 KB Output is correct
16 Correct 3 ms 8284 KB Output is correct
17 Correct 3 ms 8252 KB Output is correct
18 Correct 3 ms 8284 KB Output is correct
19 Correct 2 ms 8284 KB Output is correct
20 Correct 3 ms 8284 KB Output is correct
21 Correct 3 ms 8284 KB Output is correct
22 Correct 3 ms 8284 KB Output is correct
23 Correct 3 ms 8284 KB Output is correct
24 Correct 3 ms 8284 KB Output is correct
25 Correct 225 ms 17232 KB Output is correct
26 Correct 38 ms 12016 KB Output is correct
27 Correct 305 ms 20876 KB Output is correct
28 Correct 318 ms 20300 KB Output is correct
29 Correct 221 ms 16956 KB Output is correct
30 Correct 211 ms 20116 KB Output is correct
31 Correct 283 ms 16588 KB Output is correct
32 Correct 309 ms 19868 KB Output is correct
33 Correct 283 ms 18072 KB Output is correct
34 Correct 159 ms 17648 KB Output is correct
35 Correct 333 ms 19256 KB Output is correct
36 Correct 317 ms 20640 KB Output is correct
37 Correct 171 ms 12632 KB Output is correct
38 Correct 292 ms 17888 KB Output is correct
39 Correct 43 ms 9624 KB Output is correct
40 Correct 300 ms 17104 KB Output is correct
41 Correct 250 ms 16308 KB Output is correct
42 Correct 298 ms 16712 KB Output is correct
43 Correct 117 ms 10984 KB Output is correct
44 Correct 291 ms 17672 KB Output is correct
45 Correct 52 ms 10480 KB Output is correct
46 Correct 291 ms 17380 KB Output is correct
47 Correct 78 ms 10480 KB Output is correct
48 Correct 298 ms 18184 KB Output is correct

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 414 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 4 ms 8500 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 3 ms 8284 KB Output is correct
7 Correct 3 ms 8284 KB Output is correct
8 Correct 3 ms 8284 KB Output is correct
9 Correct 3 ms 8280 KB Output is correct
10 Correct 3 ms 8284 KB Output is correct
11 Correct 3 ms 8284 KB Output is correct
12 Correct 3 ms 8336 KB Output is correct
13 Correct 4 ms 8536 KB Output is correct
14 Correct 2 ms 8284 KB Output is correct
15 Correct 3 ms 8340 KB Output is correct
16 Correct 3 ms 8284 KB Output is correct
17 Correct 3 ms 8252 KB Output is correct
18 Correct 3 ms 8284 KB Output is correct
19 Correct 2 ms 8284 KB Output is correct
20 Correct 3 ms 8284 KB Output is correct
21 Correct 3 ms 8284 KB Output is correct
22 Correct 3 ms 8284 KB Output is correct
23 Correct 3 ms 8284 KB Output is correct
24 Correct 3 ms 8284 KB Output is correct
25 Correct 225 ms 17232 KB Output is correct
26 Correct 38 ms 12016 KB Output is correct
27 Correct 305 ms 20876 KB Output is correct
28 Correct 318 ms 20300 KB Output is correct
29 Correct 221 ms 16956 KB Output is correct
30 Correct 211 ms 20116 KB Output is correct
31 Correct 283 ms 16588 KB Output is correct
32 Correct 309 ms 19868 KB Output is correct
33 Correct 283 ms 18072 KB Output is correct
34 Correct 159 ms 17648 KB Output is correct
35 Correct 333 ms 19256 KB Output is correct
36 Correct 317 ms 20640 KB Output is correct
37 Correct 171 ms 12632 KB Output is correct
38 Correct 292 ms 17888 KB Output is correct
39 Correct 43 ms 9624 KB Output is correct
40 Correct 300 ms 17104 KB Output is correct
41 Correct 250 ms 16308 KB Output is correct
42 Correct 298 ms 16712 KB Output is correct
43 Correct 117 ms 10984 KB Output is correct
44 Correct 291 ms 17672 KB Output is correct
45 Correct 52 ms 10480 KB Output is correct
46 Correct 291 ms 17380 KB Output is correct
47 Correct 78 ms 10480 KB Output is correct
48 Correct 298 ms 18184 KB Output is correct
49 Runtime error 414 ms 524288 KB Execution killed with signal 9
50 Halted 0 ms 0 KB -