제출 #1341511

#제출 시각아이디문제언어결과실행 시간메모리
1341511sabino1Monkey and Apple-trees (IZhO12_apple)C++20
100 / 100
273 ms111624 KiB
#include <bits/stdc++.h>
using namespace std;
// #define lef(x) (x<<1)
// #define rig(x) (lef(x)|1)
#define get_bit(x,i) ((x)&(1ll<<(i)))
#define sq(x) (1ll*(x)*(x))
#define el '\n'
using ll = long long int; using ull = uint64_t; using ld = long double;
template<class T> using vc = vector<T>; template<class T> using vvc = vector<vc<T>>;
// const int MAX = 5e5+10;
const int mod = 1e9 + 7; // 998244353;
const int mod1 = 1e9+6;
const int mod2 = 1e9+5;
// const int inf = 2'000'000'000;
// const int TETO = 20;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// Indexado de 1
// Query com op associativa e update em range
// Query: 4*log(N)
// Update: 4*log(N)
// Q*log(N) de memoria
// Definir: node,sono,merge,apply,build,update
#warning verificar se tem conflito com os defines
#define lef(x) prox[x].first
#define rig(x) prox[x].second
#define inter(a,b,c,d) (!((d) < (a) || (c) > (b)))
struct Seg{
    Seg(int nn = 0) : n(nn),seg(1),lazy(1),prox(1,{0,0}){}
    // No da seg
    struct node{
        int sum;
        bool off = true;
    };
    // Update e lazy
    struct sono{
        bool off = true;
    };
    
    int n; vc<node> seg;  vc<sono> lazy;
    vc<pair<int,int>> prox;
    node ret,aux,offn;
    void merge(node &x, node &y, node &at){
        if(x.off) return void(at = y); // as vezes mudar o que o fazer com o off
        if(y.off) return void(at = x);
        // o at eh o merge do x(esq) e y(dir)
        at.sum = x.sum + y.sum;
        at.off = false;
    }
    // aplica o updt e updt lazy
    void apply(int u,int tl,int tr,sono& x){
        seg[u].off = false;
        seg[u].sum = tr-tl+1;
        lazy[u].off = false;
    }
    void push(int u,int tl,int tr){
        if(tl == tr || lazy[u].off) return;
        int tmid = tl + tr; tmid >>= 1;
        apply(lef(u),tl,tmid,lazy[u]),apply(rig(u),tmid+1,tr,lazy[u]);
        lazy[u].off = true;
    }
    int add(){
        int x = seg.size();
        seg.emplace_back(),lazy.emplace_back(),prox.emplace_back(0,0);
        return x;
    }
    void query(int u,int tl,int tr,int l, int r){
        if(l > r) return;
        if(l == tl && tr == r) return merge(aux = ret,seg[u],ret);
        if(!lef(u)) lef(u) = add(), rig(u) = add();
        push(u,tl,tr); int tmid = tl + tr; tmid >>= 1;
        query(lef(u),tl,tmid,l,min(r,tmid)),query(rig(u),tmid+1,tr,max(l,tmid+1),r);
    }
    node query(int l, int r){
        ret.off = true; query(0,1,n,l,r);
        if(ret.off) ret.sum = 0;
        return ret;
    }
    
    void update(int u, int tl, int tr, int l, int r, sono& x){
        if(l > r) return;
        if(l == tl && tr == r) return apply(u,tl,tr,x);
        if(!lef(u)) lef(u) = add(), rig(u) = add();
        push(u,tl,tr); int tmid = tl + tr; tmid >>= 1;
        update(lef(u),tl,tmid,l,min(r,tmid),x),update(rig(u),tmid+1,tr,max(l,tmid+1),r,x);
        merge(seg[lef(u)],seg[rig(u)],seg[u]);
    }
    // passa os parametros que dai vai converter pra sono
    void update(int l, int r){
        sono vals = {false}; update(0,1,n,l,r,vals);
    }
};
#undef lef
#undef rig
#undef inter

void test(){
    int q; cin >> q;
    int c = 0;
    Seg seg(1e9+10);
    for(int i=0; i<q; i++){
        int t,l,r; cin >> t >> l >> r;
        if(t == 1){
            int x = seg.query(l+c,r+c).sum;
            c = x;
            cout << x << el;
        }else seg.update(l+c,r+c);
    }
}
 
int main (){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int ttt_ = 1;
    // cin >> ttt_;
    while(ttt_--) test();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

apple.cpp:25:2: warning: #warning verificar se tem conflito com os defines [-Wcpp]
   25 | #warning verificar se tem conflito com os defines
      |  ^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...