QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#410632#8177. Sum is IntegercallmelucianWA 0ms3772kbC++141.7kb2024-05-14 10:39:402024-05-14 10:39:40

Judging History

This is the latest submission verdict.

  • [2024-05-14 10:39:40]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3772kb
  • [2024-05-14 10:39:40]
  • Submitted

answer

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct BIT {
    vector<int> tr;
    BIT (int sz) : tr(sz + 1) {}

    int p (int k) { return k & -k; }

    void update (int pos, int val) {
        for (; pos < tr.size(); pos += p(pos))
            tr[pos] += val;
    }

    int sum (int pos, int ans = 0) {
        for (; pos; pos -= p(pos)) ans += tr[pos];
        return ans;
    }

    int query (int l, int r) {
        return sum(r) - sum(l - 1);
    }
};

const ld eps = 1e-9;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    vector<ld> pre(n + 1), vec;
    vec.push_back(-1); vec.push_back(0);

    for (int i = 1; i <= n; i++) {
        int a, b; cin >> a >> b;
        a %= b, pre[i] = pre[i - 1] + ld(a) / ld(b);
        pre[i] -= ll(pre[i]);
        //cout << pre[i] << " ";
        vec.push_back(pre[i]);
    }
    sort(all(vec)); filter(vec);

    BIT tree(vec.size()); tree.update(1, 1);

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        int pos = lower_bound(all(vec), pre[i]) - vec.begin();
        int l = pos, r = pos;
        for (int step = vec.size(); step >= 1; step /= 2) {
            while (r + step < vec.size() && abs(vec[r + step] - vec[pos]) < eps) r += step;
            while (l - step >= 0 && abs(vec[l - step] - vec[pos]) < eps) l -= step;
        }
        ans += tree.query(l, r);
        tree.update(pos, 1);
    }
    cout << ans;

    return 0;
}

詳細信息

Test #1:

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

input:

4
1 6
1 3
1 2
1 2

output:

2

result:

ok "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

5
1 1
2 2
3 3
4 4
5 5

output:

15

result:

ok "15"

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3772kb

input:

2
1 99999
99999 100000

output:

1

result:

wrong answer 1st words differ - expected: '0', found: '1'