QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#534923 | #9228. ICPC Inference | ucup-team052# | WA | 164ms | 32592kb | C++23 | 3.3kb | 2024-08-27 17:29:03 | 2024-08-27 17:29:04 |
Judging History
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], mn[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); mn[i] = atom(1, seq[len]);
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(mn[i].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: 20284kb
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: 3ms
memory: 20236kb
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: 164ms
memory: 32592kb
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:
274492464276783
result:
wrong answer 1st numbers differ - expected: '274533940012863', found: '274492464276783'