oj.uz

답안 #709786

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
709786 2023-03-14T12:21:54 Z WonderfulWhale Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 1058 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

vector<pii> v[1000009];
int tab[1000009];

struct SegTree {
	const static int T = 1<<20;
	vector<pii> t[2*T];
	void build(int n) {
		for(int i=0;i<n;i++) {
			if(sz(v[i])==0) continue;
			t[i+T].pb(v[i][0]);
			for(int j=1;j<sz(v[i]);j++) {
				t[i+T].pb({v[i][j].st, max(v[i][j].nd, t[i+T].back().nd)});
			}
			//cerr << "teraz: " << i+T << "\n";
			for(pii x:t[i+T]) {
				//cerr << x.st << " " << x.nd << "\n";
			}
		}
		for(int i=T-1;i>=1;i--) {
			int l = 2*i;
			int r = 2*i+1;
			int a = 0;
			int b = 0;
			while(a!=sz(t[l])||b!=sz(t[r])) {
				if(a==sz(t[l])) {
					t[i].pb({t[r][b].st, max(t[r][b].nd, sz(t[i])?t[i].back().nd:(int)0)});
					b++;
				} else if(b==sz(t[r])) {
					t[i].pb({t[l][a].st, max(t[l][a].nd, sz(t[i])?t[i].back().nd:(int)0)});
					a++;
				} else if(t[l][a].st<=t[r][b].st) {
					t[i].pb({t[l][a].st, max(t[l][a].nd, sz(t[i])?t[i].back().nd:(int)0)});
					a++;
				} else {
					t[i].pb({t[r][b].st, max(t[r][b].nd, sz(t[i])?t[i].back().nd:(int)0)});
					b++;
				}
			}
			//cerr << "teraz: " << i << "\n";
			for(pii x:t[i]) {
				//cerr << x.st << " " << x.nd << "\n";
			}
		}
	}
	int query(int val, int l, int r, int tl=0, int tr=T-1, int v=1) {
		//cerr << "query: " << val << " "<< l << " " << r << " " << tl << " " << tr << " " << v << "\n";
		if(l > r) return 0;
		if(tl==l&&tr==r) {
			int s = -1;
			int e = sz(t[v]);
			while(e-s>1) {
				int m = (e+s)/2;
				if(t[v][m].st<=val) s = m;
				else e = m;
			}
			if(s!=-1) return t[v][s].nd;
			return 0;
		}
		int tm = (tl+tr)/2;
		return max(query(val, l, min(r, tm), tl, tm, 2*v), query(val, max(l, tm+1), r, tm+1, tr, 2*v+1));
	}
};

SegTree seg;

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, q;
	cin >> n >> q;
	for(int i=0;i<n;i++) {
		cin >> tab[i];
	}
	vector<pii> s;
	for(int i=0;i<n;i++) {
		while(sz(s)&&s.back().nd<=tab[i]) {
			s.pop_back();
		}
		if(sz(s)) {
			//cerr << "dodaje: " << tab[i]+tab[s.back().st] << " do: " << s.back().st << "\n";
			v[s.back().st].pb({i, tab[i]+tab[s.back().st]});
		}
		s.pb({i, tab[i]});
	}
	//cerr << "done\n";
	seg.build(n);
	for(int i=0;i<q;i++) {
		int l, r, k;
		cin >> l >> r >> k;
		l--;
		r--;
		cout << (seg.query(r, l, r)<=k) << "\n";
	}
}

Compilation message

sortbooks.cpp: In member function 'void SegTree::build(int64_t)':
sortbooks.cpp:26:12: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   26 |    for(pii x:t[i+T]) {
      |            ^
sortbooks.cpp:51:12: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   51 |    for(pii x:t[i]) {
      |            ^

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 73044 KB Output is correct
2 Correct 39 ms 72956 KB Output is correct
3 Correct 38 ms 73128 KB Output is correct
4 Correct 38 ms 73052 KB Output is correct
5 Correct 38 ms 73044 KB Output is correct
6 Correct 39 ms 73172 KB Output is correct
7 Correct 39 ms 73264 KB Output is correct
8 Correct 44 ms 73140 KB Output is correct
9 Correct 37 ms 73068 KB Output is correct
10 Correct 38 ms 73172 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 73044 KB Output is correct
2 Correct 39 ms 72956 KB Output is correct
3 Correct 38 ms 73128 KB Output is correct
4 Correct 38 ms 73052 KB Output is correct
5 Correct 38 ms 73044 KB Output is correct
6 Correct 39 ms 73172 KB Output is correct
7 Correct 39 ms 73264 KB Output is correct
8 Correct 44 ms 73140 KB Output is correct
9 Correct 37 ms 73068 KB Output is correct
10 Correct 38 ms 73172 KB Output is correct
11 Correct 47 ms 73636 KB Output is correct
12 Correct 45 ms 75340 KB Output is correct
13 Correct 43 ms 75220 KB Output is correct
14 Correct 57 ms 75308 KB Output is correct
15 Correct 45 ms 75404 KB Output is correct
16 Correct 43 ms 73848 KB Output is correct
17 Correct 43 ms 73384 KB Output is correct
18 Correct 43 ms 74680 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 405 ms 118164 KB Output is correct
2 Correct 331 ms 118108 KB Output is correct
3 Correct 155 ms 73916 KB Output is correct
4 Correct 167 ms 74020 KB Output is correct
5 Correct 129 ms 73908 KB Output is correct
6 Correct 118 ms 77520 KB Output is correct
7 Correct 128 ms 77648 KB Output is correct
8 Correct 148 ms 101816 KB Output is correct
9 Correct 84 ms 73232 KB Output is correct
10 Correct 148 ms 95048 KB Output is correct

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 73044 KB Output is correct
2 Correct 39 ms 72956 KB Output is correct
3 Correct 38 ms 73128 KB Output is correct
4 Correct 38 ms 73052 KB Output is correct
5 Correct 38 ms 73044 KB Output is correct
6 Correct 39 ms 73172 KB Output is correct
7 Correct 39 ms 73264 KB Output is correct
8 Correct 44 ms 73140 KB Output is correct
9 Correct 37 ms 73068 KB Output is correct
10 Correct 38 ms 73172 KB Output is correct
11 Correct 47 ms 73636 KB Output is correct
12 Correct 45 ms 75340 KB Output is correct
13 Correct 43 ms 75220 KB Output is correct
14 Correct 57 ms 75308 KB Output is correct
15 Correct 45 ms 75404 KB Output is correct
16 Correct 43 ms 73848 KB Output is correct
17 Correct 43 ms 73384 KB Output is correct
18 Correct 43 ms 74680 KB Output is correct
19 Correct 1012 ms 165436 KB Output is correct
20 Correct 1058 ms 165692 KB Output is correct
21 Correct 695 ms 165436 KB Output is correct
22 Correct 738 ms 165432 KB Output is correct
23 Correct 728 ms 165316 KB Output is correct
24 Correct 189 ms 74972 KB Output is correct
25 Correct 211 ms 74932 KB Output is correct
26 Correct 237 ms 75104 KB Output is correct
27 Correct 228 ms 74952 KB Output is correct
28 Correct 224 ms 74968 KB Output is correct
29 Correct 288 ms 74980 KB Output is correct
30 Correct 232 ms 75000 KB Output is correct
31 Correct 232 ms 75012 KB Output is correct
32 Correct 235 ms 74956 KB Output is correct
33 Correct 225 ms 74940 KB Output is correct
34 Correct 207 ms 74956 KB Output is correct
35 Correct 211 ms 74968 KB Output is correct
36 Correct 188 ms 75080 KB Output is correct
37 Correct 191 ms 75064 KB Output is correct
38 Correct 187 ms 74940 KB Output is correct
39 Correct 326 ms 105536 KB Output is correct
40 Correct 197 ms 85988 KB Output is correct
41 Correct 348 ms 122504 KB Output is correct

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 73044 KB Output is correct
2 Correct 39 ms 72956 KB Output is correct
3 Correct 38 ms 73128 KB Output is correct
4 Correct 38 ms 73052 KB Output is correct
5 Correct 38 ms 73044 KB Output is correct
6 Correct 39 ms 73172 KB Output is correct
7 Correct 39 ms 73264 KB Output is correct
8 Correct 44 ms 73140 KB Output is correct
9 Correct 37 ms 73068 KB Output is correct
10 Correct 38 ms 73172 KB Output is correct
11 Correct 47 ms 73636 KB Output is correct
12 Correct 45 ms 75340 KB Output is correct
13 Correct 43 ms 75220 KB Output is correct
14 Correct 57 ms 75308 KB Output is correct
15 Correct 45 ms 75404 KB Output is correct
16 Correct 43 ms 73848 KB Output is correct
17 Correct 43 ms 73384 KB Output is correct
18 Correct 43 ms 74680 KB Output is correct
19 Runtime error 440 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -