QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#110919#3066. Intrinsic IntervalLitDarknessWA 4ms7908kbC++142.3kb2023-06-04 19:49:022023-06-04 19:49:06

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-04 19:49:06]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:7908kb
  • [2023-06-04 19:49:02]
  • 提交

answer

#include <bits/stdc++.h>
#define For(i, a, b) for (int i = a; i <= b; ++i)
#define Rep(i, a, b) for (int i = a; i >= b; --i)
using namespace std;
const int maxN = 1e5 + 5;
struct seg_tree {
	int tg, val;
}T[maxN << 2];
int n, m;
int st1[maxN], tp1, st2[maxN], tp2, a[maxN];
int al[maxN], ar[maxN];
struct Query {
	int l, r, id;
	bool operator< (const Query &a) const { return l < a.l; }
	bool operator== (const Query &a) const { return id == a.id; }
}qu[maxN];
inline void addt(int x, int v) { T[x].tg += v; T[x].val += v; }
inline void pd(int k) {
	if (T[k].tg) {
		addt(k << 1, T[k].tg); addt(k << 1|1, T[k].tg);
		T[k].tg = 0;
	}
}
void update(int x, int y, int v, int k = 1, int l = 1, int r = n) {
	if (x <= l && r <= y) return addt(k, v);
	pd(k);
	int mid = l + r >> 1;
	if (x <= mid) update(x, y, v, k << 1, l, mid);
	if (y > mid) update(x, y, v, k << 1|1, mid + 1, r);
	T[k].val = min(T[k << 1].val, T[k << 1|1].val);
}
int query(int x, int y, int k = 1, int l = 1, int r = n) {
	if (x <= l && r <= y) return T[k].val;
	pd(k);
	int mid = l + r >> 1, s = n + 1;
	if (x <= mid) s = min(s, query(x, y, k << 1, l, mid));
	if (y > mid) s = min(s, query(x, y, k << 1|1, mid + 1, r));
	return s;
}
inline int findp(int r) {
	int l = 1, ans = -1, mid;
	if (query(1, r)) return -1;
	while (l <= r) {
		mid = l + r >> 1;
		if (query(mid, r) == 0) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	return ans;
}
set<Query> S;
int main() {
	scanf("%d", &n);
	For (i, 1, n) scanf("%d", a + i);
	scanf("%d", &m);
	For (i, 1, m) {
		scanf("%d%d", &qu[i].l, &qu[i].r); qu[i].id = i;
	}
	sort(qu + 1, qu + m + 1, [](Query a, Query b) { return a.r < b.r; });
	int tp = 1;
	For (i, 1, n) {
		while (tp1 && a[st1[tp1]] > a[i]) {
			update(st1[tp1 - 1] + 1, st1[tp1], -a[i] + a[st1[tp1]]);
			--tp1;
		}
		st1[++tp1] = i;
		while (tp2 && a[st2[tp2]] < a[i]) {
			update(st2[tp2 - 1] + 1, st2[tp2], a[i] - a[st2[tp2]]);
			--tp2;
		}
		st2[++tp2] = i;
		if (i > 1) update(1, i - 1, -1);
		while (tp <= m && qu[tp].r == i) S.emplace(qu[tp++]);
		while (!S.empty()) {
			auto v = *S.rbegin();
			int u = findp(v.l);
			if (u == -1) break;
			al[v.id] = u; ar[v.id] = i;
			S.erase(*S.rbegin());
		}
	}
	For (i, 1, m) printf("%d %d\n", al[i], ar[i]);
	return 0;
} 

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 5876kb

input:

7
3 1 7 5 6 4 2
3
3 6
7 7
1 3

output:

3 6
7 7
1 7

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 5852kb

input:

10
2 1 4 3 5 6 7 10 8 9
5
2 3
3 7
4 7
4 8
7 8

output:

1 4
3 7
3 7
3 10
7 10

result:

ok 5 lines

Test #3:

score: 0
Accepted
time: 4ms
memory: 5688kb

input:

1000
998 996 997 1000 999 991 992 994 995 993 986 987 988 989 990 984 983 981 985 982 979 977 976 978 980 975 973 974 972 971 964 962 963 965 961 970 966 967 969 968 848 849 850 846 847 842 841 843 845 844 853 851 855 854 852 858 860 857 856 859 869 867 866 868 870 865 864 862 861 863 874 871 875 87...

output:

1 3
2 3
1 5
4 5
1 10
6 7
7 10
8 9
8 10
6 15
11 12
12 13
13 14
14 15
11 20
16 17
16 20
16 20
16 20
16 25
21 24
22 23
22 24
21 25
21 26
26 28
27 28
27 29
29 30
30 40
31 33
32 33
31 34
31 35
31 40
36 40
37 38
38 40
39 40
31 200
41 42
42 43
41 45
44 45
44 50
46 47
46 48
48 50
49 50
41 55
51 55
51 55
53 ...

result:

ok 999 lines

Test #4:

score: -100
Wrong Answer
time: 4ms
memory: 7908kb

input:

1000
993 992 994 995 991 998 996 1000 999 997 988 987 986 989 990 985 984 981 982 983 963 962 964 965 961 967 968 970 969 966 972 975 973 974 971 977 980 976 979 978 940 937 936 938 939 933 932 931 934 935 923 924 925 922 921 929 926 927 928 930 953 954 955 951 952 956 958 959 960 957 948 950 947 94...

output:

21 1000
201 1000
21 1000
81 1000
201 1000
17 1000
201 1000
121 1000
41 1000
11 1000
201 1000
0 0
41 1000
81 1000
81 1000
201 1000
0 0
481 900
0 0
361 680
1 1000
201 1000
121 1000
201 1000
201 1000
481 680
121 1000
121 1000
41 1000
441 840
121 1000
361 1000
201 1000
361 680
0 0
361 1000
361 680
361 5...

result:

wrong answer 12th lines differ - expected: '201 1000', found: '0 0'