Submission #877431

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
877431	2023-11-23T08:37:14 Z	MDSPro	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	31 ms	34140 KB

apple

// MDSPro
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

const ld PI = 3.141592653589793;
const int MOD = 1e9+7;
const int INF = 1e9;
const ll INFLL = 4e18;
const double EPS = 1e-9;
const int MAXN = 1000*1007;

// Segment Tree structure.
// Top to bottom. Version 2.5.0
// change:
//      Node structure 
//      Constructor (if need)
//      Add extra interface functions (if need)

// NOTE: indexation of tree nodes from 1
//       indexation of range (array elements) from 0
//       work with semi-interval, a.k.a [l,r)

// Type of queries:
// save - max; propogate - apply; find - smaller or equal;
struct SegTree{
    struct Node{
        // node variables.
        ll sum,apply;
        
        // neutral element.
        Node(){
            sum = 0, apply = -1;
        }
        
        // gets value from array.
        Node operator=(const ll x){
            sum = 0, apply = -1;
            return *this;
        }
        
        // merges two sons to mother.
        void merge(const Node &a, const Node &b, int len = 0){
            sum = a.sum + b.sum;
        }
        
        // splits update from mother to sons.
        void split(Node &a, Node &b, int len = 0){
            if(apply != -1){
                a.impact(apply,len>>1);
                b.impact(apply,len>>1);
                apply = -1;
            }
        }
        
        // updates.
        void impact(ll v, int len = 0){
            sum = v * len;
            apply = v;
        }
    };
    
    // variables: tree, neutral element and sizes.
    vector<Node> tree;
    Node NEUTRAL;
    int n,N;
    
    // constructor: uses to build segment tree.
    SegTree(vector<ll> &a){
        n = a.size();
        N = 1<<(32-__builtin_clz(n-1));
        tree.resize(2*N);
        
        for(int i = N; i < N+n; ++i) tree[i] = a[i-N];
        for(int i = N-1; i > 0; --i) tree[i].merge(tree[i<<1],tree[i<<1|1]);
    }
    
    SegTree(int sz){
        n = sz;
        N = 1<<(32-__builtin_clz(n-1));
        tree.resize(2*N);
        
        for(int i = N-1; i > 0; --i) tree[i].merge(tree[i<<1],tree[i<<1|1]);
    }

    // for there and after
    // [ql,qr) asking range
    // i       node number
    // [l,r)   range of the node
    
    // range_query: calculates everything on range.
    Node range_query(int i, int l, int r, int ql, int qr){
        if(qr <= l || r <= ql) return NEUTRAL;
        if(ql <= l && r <= qr) return tree[i];
        
        tree[i].split(tree[i<<1],tree[i<<1|1],r-l);
        int mid = (l+r)>>1;
        
        Node ans;
        ans.merge(range_query(i<<1  ,l,mid,ql,qr),
                  range_query(i<<1|1,mid,r,ql,qr),
                  r-l);
        return ans;
    }
    
    // interface to range_query:
    // call range_query then ask anything.
    ll sum(int ql, int qr){
        Node ans = range_query(1,0,N,ql,qr);
        return ans.sum;
    }
    
    // range_update: updates the range with parameter v.
    void range_update(int i, int l, int r, int ql, int qr, ll v){
        if(qr <= l || r <= ql) return;
        if(ql <= l && r <= qr) {
            tree[i].impact(v,r-l);
            return;
        }
        
        int mid = (l+r)>>1;
        tree[i].split(tree[i<<1],tree[i<<1|1],r-l);
        range_update(i<<1,  l,mid,ql,qr,v);
        range_update(i<<1|1,mid,r,ql,qr,v);
        tree[i].merge(tree[i<<1],tree[i<<1|1],r-l);
    }

    // interface for range_update:
    // change name not to confuse.
    void apply(int ql, int qr, ll v){
        range_update(1,0,N,ql,qr,v);
    }
};


void solve(int NT){
    SegTree sg(MAXN);

    int q; cin >> q;
    int C = 0;
    while(q--) {
        int d, x, y; cin >> d >> x >> y;
        x += C; y += C;
        if(d == 1) {
            C = sg.sum(x, y + 1);
            cout << C << '\n';
        } else {
            sg.apply(x, y + 1, 1);
        }
    }
}

// #define TESTCASES
int main() {
    cin.tie(0)->sync_with_stdio(0);

    int t = 1;
    #ifdef TESTCASES
        cin >> t;
    #endif
    
    for(int i = 1; i <= t; ++i){
        solve(i);
        cout << "\n";
    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	33116 KB	Output is correct
2	Correct	8 ms	33116 KB	Output is correct
3	Correct	9 ms	33112 KB	Output is correct
4	Correct	13 ms	33368 KB	Output is correct
5	Correct	15 ms	33420 KB	Output is correct
6	Correct	14 ms	33372 KB	Output is correct
7	Correct	15 ms	33316 KB	Output is correct
8	Incorrect	31 ms	34140 KB	Output isn't correct
9	Halted	0 ms	0 KB	-