oj.uz

답안 #399228

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
399228 2021-05-05T12:52:43 Z abacaba Sum Zero (RMI20_sumzero) C++17
100 / 100
 896 ms 18208 KB 
// 石室詩士施氏, 嗜獅, 誓食十獅。
// 氏時時適市視獅。
// 十時, 適十獅適市。
// 是時, 適施氏適市。
// 氏視是十獅, 恃矢勢, 使是十獅逝世。
// 氏拾是十獅屍, 適石室。
// 石室濕, 氏使侍拭石室。
// 石室拭, 氏始試食是十獅。
// 食時, 始識是十獅, 實十石獅屍。
// 試釋是事。
 
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define f first
#define se second
 
template <typename T> void Max(T &a, T b) {
	a = max(a, b);
}
 
template <typename T> void Min(T &a, T b) {
	a = min(a, b);
}
 
const int inf = 0x3f3f3f3f;
const int N = 4e5 + 2;
int n, q, p[N], to[N];
int qs[N], last[N];
int l, r, mid;
int sz, i, ind;
int R[N], prv[N], head[N], prvqs[N];
 
inline void dfs(int v) {
	to[sz++] = v;
	for(i = qs[v]; i != -1; i = last[i]) {
		l = 0, r = sz - 1;
		p[i] = -inf;
		while(l <= r) {
			mid = l + r >> 1;
			if(to[mid] <= R[i])
				r = mid - 1, Max(p[i], sz - mid - 1);
			else
				l = mid + 1;
		}
	}
	for(int to = head[v]; to != -1; to = prv[to])
		dfs(to);
	--sz;
}
 
int main() {
	memset(head, -1, sizeof(head));
	memset(prv, -1, sizeof(prv));
	memset(qs, -1, sizeof(qs));
	memset(prvqs, -1, sizeof(prvqs));
	memset(last, -1, sizeof(last));
	ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
	// freopen("input.txt", "r", stdin);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> p[i];
		p[i] += p[i-1];
		qs[i] = p[i];
	}
	qs[0] = 0;
	sort(qs, qs + n + 1);
	fill(to, to + n + 2, n + 1);
	for(i = n; i >= 0; --i) {
		ind = lower_bound(qs, qs + n + 1, p[i]) - qs;
		if(last[ind] != -1)
			Min(to[i], last[ind]);
		Min(to[i], to[i+1]);
		prv[i] = head[to[i]];
		head[to[i]] = i;
		last[ind] = i;
	}
	memset(qs, -1, sizeof(qs));
	memset(last, -1, sizeof(last));
	cin >> q;
	for(i = 1; i <= q; ++i) {
		cin >> l >> R[i];
		last[i] = qs[l - 1];
		qs[l - 1] = i;
	}
	dfs(n + 1);
	for(int i = 1; i <= q; ++i)
		cout << p[i] << endl;
	return 0;
}

Compilation message

sumzero.cpp: In function 'void dfs(int)':
sumzero.cpp:47:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |    mid = l + r >> 1;
      |          ~~^~~

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 8268 KB Output is correct
2 Correct 14 ms 8244 KB Output is correct
3 Correct 14 ms 8256 KB Output is correct
4 Correct 14 ms 8268 KB Output is correct
5 Correct 15 ms 8140 KB Output is correct
6 Correct 14 ms 8268 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 8268 KB Output is correct
2 Correct 14 ms 8244 KB Output is correct
3 Correct 14 ms 8256 KB Output is correct
4 Correct 14 ms 8268 KB Output is correct
5 Correct 15 ms 8140 KB Output is correct
6 Correct 14 ms 8268 KB Output is correct
7 Correct 212 ms 10616 KB Output is correct
8 Correct 205 ms 9900 KB Output is correct
9 Correct 219 ms 10336 KB Output is correct
10 Correct 210 ms 10612 KB Output is correct
11 Correct 208 ms 9924 KB Output is correct
12 Correct 220 ms 10308 KB Output is correct

Subtask #3
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 8268 KB Output is correct
2 Correct 14 ms 8244 KB Output is correct
3 Correct 14 ms 8256 KB Output is correct
4 Correct 14 ms 8268 KB Output is correct
5 Correct 15 ms 8140 KB Output is correct
6 Correct 14 ms 8268 KB Output is correct
7 Correct 212 ms 10616 KB Output is correct
8 Correct 205 ms 9900 KB Output is correct
9 Correct 219 ms 10336 KB Output is correct
10 Correct 210 ms 10612 KB Output is correct
11 Correct 208 ms 9924 KB Output is correct
12 Correct 220 ms 10308 KB Output is correct
13 Correct 858 ms 18208 KB Output is correct
14 Correct 848 ms 15432 KB Output is correct
15 Correct 894 ms 17216 KB Output is correct
16 Correct 851 ms 17616 KB Output is correct
17 Correct 833 ms 15516 KB Output is correct
18 Correct 896 ms 17300 KB Output is correct