QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#534913#9228. ICPC Inferenceucup-team052#WA 176ms30864kbC++233.2kb2024-08-27 17:25:052024-08-27 17:25:05

Judging History

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

  • [2024-08-27 17:25:05]
  • 评测
  • 测评结果:WA
  • 用时:176ms
  • 内存:30864kb
  • [2024-08-27 17:25:05]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef pair <int, int> pii;
typedef long long ll;

const int N = 2e5 + 5;

struct atom {
	int n, t;
	atom (int a = 0, int b = 0) : n(a), t(b) {}
	bool operator < (const atom &A) const {	
		if (n != A.n) return n < A.n;
		return t > A.t;
	}
};

multiset < pair <atom, int> > all;
vector <int> a[N];
vector <atom> b[N];
atom mx[N];
int id[N], seq[N], now[N], len;
int n, d, l; ll ans, sum;

bool cmp(int i, int j) {
	return mx[i] < mx[j];
}

int calc(atom x) {
	if (x.n >= 2) return len - 1;
	int pos = lower_bound(seq + 1, seq + len + 1, x.t) - seq;
	return len - pos;
}

const int M = 5e6;

int f[M];

void add(int x, int y) {
	while (x < M) {
		f[x] += y;
		x += (x & -x);
	}
}

int query(int x) {
	int ans = 0;
	while (x) {
		ans += f[x];
		x &= (x - 1);
	}
	return ans;
}

int main() {
	scanf("%d%d%d", &n, &d, &l);
	for (int i = 1; i <= n; i++) {
		int id, t;
		scanf("%d%d", &id, &t);
		a[id].push_back(t);
	}
	for (int i = 1; i <= d; i++) {
		if (a[i].size()) {
			vector <pii> seg[20];
			seq[++len] = a[i].back() + (a[i].size() - 1) * 20; id[len] = i; mx[i] = atom(0, 0);
			if ((int)a[i].size() >= 2) b[i].push_back(atom(2, a[i][(int)a[i].size() - 2] + a[i].back() + (a[i].size() - 2) * 20));
			int cnt = 0;
			for (auto j : a[i]) {
				// b[i].push_back(atom(1, j + cnt * 20)); ++cnt;
				seg[j % 20].emplace_back(j, j + cnt * 20); ++cnt;
				if (mx[i].n <= 5) {
					++mx[i].n;
					mx[i].t += j;
				}
			}
			for (int j = 0; j < 20; j++) {
				int now = 0, x = j;
				while (now < (int)seg[j].size() && x <= l) {
					if (seg[j][now].second < x) ++now;
					else {
						x = max(x, seg[j][now].first);
						if (x > l) break;
						b[i].push_back(atom(1, x));
						x += 20;
					}
				}
			}
			stable_sort(b[i].begin(), b[i].end());
			reverse(b[i].begin(), b[i].end());
			all.insert(make_pair(b[i][0], i));
			if (b[i][0].n == 1) add(b[i][0].t, 1);
		}
	}
	sort(id + 1, id + len + 1, cmp);
	sort(seq + 1, seq + len + 1);
	for (int i = 1; i <= d; i++) {
		if (b[i].size()) sum += calc(b[i][0]);
	}
	// fprintf(stderr, "sum = %lld, len = %d\n", sum, len);
	for (int _ = len; _ >= 1; _--) {
		int i = id[_];
		// fprintf(stderr, "i = %d\n", i);
		while (all.size()) {
			auto it = --all.end();
			if (mx[i] < it -> first) {
				++now[it -> second];
				sum -= calc(it -> first);
				// fprintf(stderr, "calc({%d, %d}} = %d\n", (it -> first).n, (it -> first).t, calc(it -> first));
				if ((it -> first).n == 1) add((it -> first).t, -1);
				if (now[it -> second] < (int)b[it -> second].size()) {
					all.insert(make_pair(b[it -> second][now[it -> second]], it -> second));
					sum += calc(b[it -> second][now[it -> second]]);
					// fprintf(stderr, "calc({%d, %d}) = %d\n", b[it -> second][now[it -> second]].n, b[it -> second][now[it -> second]].t, calc(b[it -> second][now[it -> second]]));
					if (b[it -> second][now[it -> second]].n == 1) add(b[it -> second][now[it -> second]].t, 1);
				}
				all.erase(it);
			} else break;
		}
		ans += sum - calc(b[i][now[i]]);
		// fprintf(stderr, "ans = %lld\n", ans);
		ans -= ((int)all.size() - 1 - query(M - 1) + query(b[i].back().t));
	}
	printf("%lld\n", ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 18128kb

input:

4 3 300
1 10
2 25
2 30
3 50

output:

3

result:

ok 1 number(s): "3"

Test #2:

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

input:

4 6 200000
6 1
6 1
1 2
2 2

output:

4

result:

ok 1 number(s): "4"

Test #3:

score: -100
Wrong Answer
time: 176ms
memory: 30864kb

input:

191580 64997 56
24878 1
35060 1
24245 1
64330 1
9650 1
15423 1
34953 1
21456 1
36718 1
21395 1
17613 1
16995 1
45257 1
31277 1
20026 1
1870 1
25581 1
9997 1
54701 1
30752 1
32269 1
705 1
64186 1
58881 1
24614 1
55311 1
18259 1
58886 1
23296 1
17628 1
3411 1
37469 1
47951 1
12188 1
60720 1
54168 1
45...

output:

274492464987114

result:

wrong answer 1st numbers differ - expected: '274533940012863', found: '274492464987114'