Submission #1162167

#TimeUsernameProblemLanguageResultExecution timeMemory
1162167with_wageehMonkey and Apple-trees (IZhO12_apple)C++20
0 / 100
633 ms320 KiB
#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
#define endl '\n'
#define wageh ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(0)
#define loop(i, n) for (int i=0;i<int(n);i++)
#define rep(k, n) for (int k=1 ;k<= long long (n);k++)
#define ll long long
#define ld long double
#define all(x) x.begin(),x.end()
#define vec  vector<ll>
#define stt stack<ll>
#define dqq deque<ll>
#define pi pair<int,int>
#define pl pair<ll,ll>
#define vecp  vector<pair<ll,ll>>
#define memo(v, d) memset(v, d , sizeof(v))
int fx[] = {0, 0, 1, -1, -1, 1, -1, 1};
int fy[] = {1, -1, 0, 0, 1, 1, -1, -1};
char dir[] = {'R', 'L', 'D', 'U'};
const double PI = 3.14159265359;
const int N = 2e5 + 2;

ll fast_pow_mod(ll base, ll power, ll mod) {
    ll res = 1;
    while (power > 0) {
        if (power & 1)res = ((res % mod) * (base % mod)) % mod;
        base *= base;
        base %= mod;
        power /= 2;
    }
    return res;
}

const int mod = 998244353;

ll add(ll x, ll a) { return ((a % mod) + (x % mod)) % mod; }

ll mul(ll a, ll b) { return ((a % mod) * (b % mod)) % mod; }

ll sub(ll a, ll b) { return ((a % mod) - (b % mod) + mod) % mod; }

ll inv(ll a) { return fast_pow_mod(a, mod - 1, mod); }


class SparseSegtree {
private:
    struct Node {
        int freq = 0;
        int lazy = 0;
        int left = -1;
        int right = -1;
    };
    vector<Node> tree;
    const int n;
    int timer = 0;

    int comb(int a, int b) { return a + b; }

    void apply(int cur, int len, int val) {
        if (val == 1) {
            tree[cur].lazy = val;
            tree[cur].freq = len * val;
        }
    }

    void push_down(int cur, int l, int r) {
        if (tree[cur].left == -1) {
            tree[cur].left = ++timer;
            tree.push_back(Node());
        }
        if (tree[cur].right == -1) {
            tree[cur].right = ++timer;
            tree.push_back(Node());
        }
        int m = (l + r) / 2;
        apply(tree[cur].left, m - l + 1, tree[cur].lazy);
        apply(tree[cur].right, r - m, tree[cur].lazy);
        tree[cur].lazy = 0;
    }

    void range_set(int cur, int l, int r, int ql, int qr, int val) {
        if (qr < l || ql > r) { return; }
        if (ql <= l && r <= qr) {
            apply(cur, r - l + 1, val);
        } else {
            push_down(cur, l, r);
            int m = (l + r) / 2;
            range_set(tree[cur].left, l, m, ql, qr, val);
            range_set(tree[cur].right, m + 1, r, ql, qr, val);
            tree[cur].freq =
                    comb(tree[tree[cur].left].freq, tree[tree[cur].right].freq);
        }
    }

    int range_sum(int cur, int l, int r, int ql, int qr) {
        if (qr < l || ql > r) { return 0; }
        if (ql <= l && r <= qr) { return tree[cur].freq; }
        push_down(cur, l, r);
        int m = (l + r) / 2;
        return comb(range_sum(tree[cur].left, l, m, ql, qr),
                    range_sum(tree[cur].right, m + 1, r, ql, qr));
    }

public:
    SparseSegtree(int n, int q = 0) : n(n) {
        if (q > 0) { tree.reserve(2 * q * __lg(n)); }
        tree.push_back(Node());
    }

    void range_set(int ql, int qr, int val) { range_set(0, 0, n - 1, ql, qr, val); }

    int range_sum(int ql, int qr) { return range_sum(0, 0, n - 1, ql, qr); }
};

signed main() {
    wageh;

    freopen("f.in", "r", stdin);
    freopen("f.in", "w", stdout);
    int t = 1;
    // cin >> t;
    while (t--) {
   int n ; cin >> n ;
   SparseSegtree sp ((int)1e9 + 1);
   int c = 0;
        for (int i = 0; i < n ; ++i) {
            int type ; cin >> type;
            if(type == 1){
                int l , r ; cin >> l >> r;
             c = sp.range_sum(l + c, r+ c);
             cout << c << endl;
            }
            else{
                int l , r ; cin >> l >> r;
                sp.range_set(l + c , r + c , 1);
            }

        }




    }
}

Compilation message (stderr)

apple.cpp: In function 'int main()':
apple.cpp:125:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |     freopen("f.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
apple.cpp:126:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |     freopen("f.in", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...