QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#880885 | #8035. Call Me Call Me | gsn531 | WA | 93ms | 936800kb | C++26 | 4.4kb | 2025-02-03 22:32:11 | 2025-02-03 22:32:12 |
Judging History
This is the latest submission verdict.
- [2025-02-06 18:39:16]
- hack成功,自动添加数据
- (/hack/1529)
- [2025-02-03 22:32:11]
- Submitted
answer
#include<bits/stdc++.h>
using namespace std;
//18
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define fi first
#define se second
#define mkp make_pair
#define tt T[dep]
bool Mst;
const int maxn = 4e5 + 5, inf = 1e9;
int n;
struct node{
int l, r, k;
}a[maxn];
struct SGT{
pii t[maxn << 2]; int tg[maxn << 2], rc[maxn];
set<pii> q[maxn], qr[maxn];
vector<pii> D;
#define ls (x << 1)
#define rs (x << 1 | 1)
inline void up(int x){ t[x] = min(t[ls], t[rs]); }
inline void mo(int x, int v){ t[x].fi += v; tg[x] += v; }
inline void dw(int x){
mo(ls, tg[x]), mo(rs, tg[x]); tg[x] = 0;
}
inline void build(int x, int l, int r){
if(l == r) return t[x] = mkp((*q[l].begin()).fi, l), tg[x] = 0, rc[l] = x, void();
int mid = l + r >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
up(x);
}
inline void init(){
rep(i, 1, n) q[i].insert(mkp(inf, inf)), qr[i].insert(mkp(inf, inf));
build(1, 1, n);
}
inline void updtr(int x, int l, int r, int L, int R, int v){
if(l >= L and r <= R) return mo(x, v), void();
int mid = l + r >> 1; dw(x);
if(L <= mid) updtr(ls, l, mid, L, R, v); if(R > mid) updtr(rs, mid + 1, r, L, R, v);
up(x);
}
inline void updtp(int x, int l, int r, int p, int id, int val){
if(l == r){
int nat = (*q[l].begin()).fi - t[x].fi;
pii dmd = *qr[l].lower_bound(mkp(id, -inf));
qr[l].erase(dmd), q[l].erase(mkp(dmd.se, dmd.fi));
if(val)
qr[l].insert(mkp(id, val)), q[l].insert(mkp(val, id));
t[x].fi = (*q[l].begin()).fi - nat;
return;
}
int mid = l + r >> 1; dw(x);
if(p <= mid) updtp(ls, l, mid, p, id, val);
else updtp(rs, mid + 1, r, p, id, val);
up(x);
}
}T[18];
inline void Solve(int dep, int L, int R, vector<int> &S){
if(L > R or !S.size()) return;
if(L == R){
tt.D.push_back(mkp(L, R));
for(int i : S)
tt.q[L].insert(mkp((a[i].k + 1) / 2, i)),
tt.qr[L].insert(mkp(i, (a[i].k + 1) / 2));
return;
}
int mid = L + R >> 1;
tt.D.push_back(mkp(L, R));
vector<int> Ls, Rs;
for(int i : S){
if(a[i].r <= mid){ Ls.push_back(i); continue; }
if(a[i].l > mid){ Rs.push_back(i); continue; }
tt.q[a[i].l].insert(mkp((a[i].k + 1) / 2, i));
tt.qr[a[i].l].insert(mkp(i, (a[i].k + 1) / 2));
tt.q[a[i].r].insert(mkp((a[i].k + 1) / 2, i));
tt.qr[a[i].r].insert(mkp(i, (a[i].k + 1) / 2));
}
Solve(dep + 1, L, mid, Ls), Solve(dep + 1, mid + 1, R, Rs);
}
int Ans, inq[30];
inline void calc(){
int lmt = 0; while(T[lmt + 1].D.size()) ++lmt;
queue<int> q;
rep(i, 1, lmt) if(T[i].t[1].fi <= 0) q.push(i), inq[i] = 1;
while(q.size()){
int dep = q.front(); q.pop(); inq[dep] = 0;
int pos = tt.t[1].se;//l or r
int id = (*tt.q[pos].begin()).se;
int l = a[id].l, r = a[id].r, k = a[id].k;
int natl = (*tt.q[l].begin()).fi - tt.t[tt.rc[l]].fi;
int natr = (*tt.q[r].begin()).fi - tt.t[tt.rc[r]].fi;
k = max(0, k - natl - natr); k = (k + 1) / 2;
tt.updtp(1, 1, n, l, id, k), tt.updtp(1, 1, n, r, id, k);
if(!k){
++Ans;
rep(i, 1, lmt){
pii d = *prev(upper_bound(T[i].D.begin(), T[i].D.end(), mkp(id, id)));
if(!(d.fi <= id and d.se >= id)) continue;
int mid = d.fi + d.se >> 1;
if(id > mid) T[i].updtr(1, 1, n, id, d.se, -1);//注意贡献不同!!!!
else T[i].updtr(1, 1, n, d.fi, id, -1);
if(T[i].t[1].fi <= 0 and !inq[i])
inq[i] = 1, q.push(i);
}
}
}
}
bool Med;
signed main(){
ios_base::sync_with_stdio(0); cin.tie(NULL);
// fprintf(stderr, "%.2lfMB\n", abs(&Mst - &Med) / 1024. / 1024.);
cin >> n;
rep(i, 1, n) cin >> a[i].l >> a[i].r >> a[i].k;
vector<int> tmp; rep(i, 1, n) tmp.push_back(i);
Solve(1, 1, n, tmp);
rep(i, 1, 17) T[i].init(), sort(T[i].D.begin(), T[i].D.end());
calc();
cout << Ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 93ms
memory: 936800kb
input:
3 2 3 2 2 3 1 2 2 0
output:
1
result:
wrong answer 1st numbers differ - expected: '3', found: '1'