QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1529#448887#8035. Call Me Call MeMoyoufairyqq28Success!2025-02-06 18:38:392025-02-06 18:38:39

Details

Extra Test:

Time Limit Exceeded

input:

400000
1 399999 0
1 399999 1
1 399999 2
1 399999 3
1 399999 4
1 399999 5
1 399999 6
1 399999 7
1 399999 8
1 399999 9
1 399999 10
1 399999 11
1 399999 12
1 399999 13
1 399999 14
1 399999 15
1 399999 16
1 399999 17
1 399999 18
1 399999 19
1 399999 20
1 399999 21
1 399999 22
1 399999 23
1 399999 24
1 3...

output:


result:


IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#448887#8035. Call Me Call Mefairyqq28TL 1804ms67572kbC++141.7kb2024-06-20 11:08:022025-02-06 19:00:04

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<cassert>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)/2)
using namespace std;
const int N = 400010;
int k[N], ans;
queue<int> q;

class TREE{
    vector<int> t[N<<2];
    void update(int u){
        for(auto i = t[u].begin(); i != t[u].end(); ){
            if(!k[*i]) i = t[u].erase(i);
            else if(!--k[*i]) q.push(*i), i = t[u].erase(i);
            else i++;
        }
    }
    public:
    void upd(int u, int l, int r, int x, int y, int id){
        if(x <= l && r <= y) return t[u].push_back(id);
        if(x <= mid) upd(ls, l, mid, x, y, id);
        if(y > mid) upd(rs, mid + 1, r, x, y, id);
    }
    void del(int u, int l, int r, int x){
        update(u);
        if(l == r) return;
        if(x <= mid) del(ls, l, mid, x);
        else del(rs, mid + 1, r, x);
    }
} tr;


int n, z[N];
void del(int x){
    z[x]++;
    tr.del(1, 1, n, x);
}

int B, l[N], r[N];
void update(bool flg = 0){
    rep(i, 1, n) z[i] += z[i-1];
    rep(i, 1, n) if(flg || k[i] > B){
        k[i] -= (z[r[i]] - z[l[i] - 1]);
        if(k[i] <= B) tr.upd(1, 1, n, l[i], r[i], i);
    }
    rep(i, 1, n) z[i] = 0;
}
int main(){
    scanf("%d", &n); B = sqrt(n);
    rep(i, 1, n){
        scanf("%d%d%d", &l[i], &r[i], &k[i]);
        k[i] = k[i];
        if(!k[i]) q.push(i);
    }
    update(1);
    int tmp = 0;
    while(!q.empty()){
        tmp++, ans++; int x = q.front(); q.pop();
        del(x);
        if(tmp == B) tmp = 0, update();
    }
    printf("%d\n", ans);
    return 0;
}