QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#177318#6879. TeyberrsPPP#AC ✓763ms41432kbC++173.2kb2023-09-12 20:34:402023-09-12 20:34:41

Judging History

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

  • [2023-09-12 20:34:41]
  • 评测
  • 测评结果:AC
  • 用时:763ms
  • 内存:41432kb
  • [2023-09-12 20:34:40]
  • 提交

answer

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int n, q, s;
const int maxN = 4e5 + 10;
int a[maxN], b[maxN], l[maxN], r[maxN];
int x[maxN], y[maxN];
vector<pair<int,int>> ask[maxN];
ll fenw[2][maxN];
int N;
void upd(ll *fenw, int v, int by) {
    while (v <= N) {
        fenw[v] += by;
        v = (v | (v - 1)) + 1;
    }
}
ll get(ll *fenw, int r) {
    ll ans = 0;
    while (r > 0) {
        ans += fenw[r];
        r &= (r - 1);
    }
    return ans;
}

int lower_bound(ll* fenw, ll lim) {
    int lg = 21;
    int res = 0;
    for (int k = lg; k >= 0; k--) {
        int p = (res + (1 << k));
        if (p <= N && fenw[p] < lim) {
            lim -= fenw[p];
            res += (1 << k);
        }
    }
    return res + 1;
}
ll ans[maxN];
void solve() {
    cin >> n >> q >> s;
    vector<pair<int,int>> ps;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> l[i] >> r[i];
        l[i] += i;
        r[i] += i;
        ps.emplace_back(b[i] - a[i], i);
        ask[i].clear();
    }
    sort(ps.begin(), ps.end());
    N = ps.size();
    for (int i = 1; i <= N; i++) {
        fenw[0][i] = fenw[1][i] = 0;
    }
    for (int i = 1; i <= q; i++) {
        cin >> x[i] >> y[i];
        ans[i] = -1;
        ask[x[i]].emplace_back(x[i] + y[i], i);
    }
    int L = s;
    int R = s;
    ll add = 0;
    int SZ = 0;
    for (int i = 1; i <= n; i++) {
        add += a[i];
        int t = lower_bound(ps.begin(), ps.end(), make_pair(b[i] - a[i], i)) - ps.begin() + 1;
//        cout << " UPD " << t << endl;
        upd(fenw[0], t, 1);
        upd(fenw[1], t, b[i] - a[i]);
        SZ++;
//        cout << " HI " << i << " " << SZ << endl;
        R += 2;
        while (L < l[i] && L < R) {
            int T = lower_bound(fenw[0], 1);
            upd(fenw[0], T, -1);
            upd(fenw[1], T, -ps[T - 1].first);
            add += ps[T - 1].first;
            L += 2;
            SZ--;
        }
        while (R > r[i] && L < R) {
            int T = lower_bound(fenw[0], SZ);
//            cout << T << " " << ps.size() << " ???? " <<  ;
            upd(fenw[0], T, -1);
            upd(fenw[1], T, -ps[T - 1].first);
            R -= 2;
            SZ--;
        }
        if (L < l[i] || R > r[i]) break;
        for (auto& it : ask[i]) {
//            if (i == 2 && it.first == 3) {
//                cout << " HIHI " << L << " " <
//            }
            if (it.first % 2 != L % 2) continue;
            if (it.first < L || it.first > R) continue;
            int take = (it.first - L) / 2;
            if (take == 0) {
                ans[it.second] = add;
            }
            else {
                int T = lower_bound(fenw[0], take);
                ans[it.second] = get(fenw[1], T) + add;
            }
        }
    }
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    int tst;
    cin >> tst;
    while (tst--) {
        solve();
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 763ms
memory: 41432kb

input:

195
1000 1000 390
165421182 830456752 1 1000
629019981 620808876 1 1000
62707726 251768991 1 1000
844654415 296391973 1 1000
836363753 361815634 1 1000
642057941 223752937 1 1000
527067969 5380815 1 1000
450406115 259514303 1 1000
24141454 47050814 1 1000
43169027 396162770 1 1000
251099657 45559691...

output:

92752413572
148125233324
-1
-1
88499313425
233473977168
-1
238802954522
143738626894
107917385972
-1
-1
-1
-1
-1
284051155851
-1
-1
169514189469
-1
-1
-1
-1
-1
-1
302793061319
-1
321552962401
-1
303271376461
-1
-1
60964760583
-1
-1
-1
-1
-1
49596109472
192661061222
173094083467
-1
125418958455
-1
-1...

result:

ok 990000 lines