QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#177318 | #6879. Teyberrs | PPP# | AC ✓ | 763ms | 41432kb | C++17 | 3.2kb | 2023-09-12 20:34:40 | 2023-09-12 20:34:41 |
Judging History
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