Submission #1268872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268872		abel2008	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	0 ms	320 KiB

apple

#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("f.in");
ofstream fout("f.out");
int m,op,st,dr,c = 0,ans;
const int n = 1000000009;

struct Node {
    int sum = 0;
    // lazy is a bool that shows if the segment is to be painted
    int lazy = 0;
    Node *left = nullptr;
    Node *right = nullptr;
};

Node *root = new Node;

void propagate(Node*& node,int l,int r) {
        if (l==r)
                return ;
        if (node->lazy==0)
                return ;
        if (node->left==nullptr)
                node->left = new Node();
        if (node->right==nullptr)
                node->right = new Node();
        int mid = (l+r)/2;
        node->left->lazy = 1;
        node->right->lazy = 1;

        node->left->sum = mid-l+1;
        node->right->sum = r-mid;

        node->lazy = 0;
}

void update(Node*& node,int l,int r) {
        propagate(node,l,r);
        if (r<st||l>dr) {
                return ;
        }
        if (l>=st&&r<=dr) {
                // we need to riped them
                node->lazy = 1;
                node->sum = r-l+1;
                return ;
        }
        int mid = (l+r)/2;
        if (node->left==nullptr)
                node->left = new Node();
        if (node->right==nullptr)
                node->right = new Node();
        update(node->left,l,mid);
        update(node->right,mid+1,r);
        node->sum = node->left->sum+node->right->sum;
}

void query(Node*& node,int l,int r) {
        propagate(node,l,r);
        if (r<st||l>dr)
                return ;
        if (l>=st&&r<=dr) {
                ans+=(node->sum);
                return ;
        }
        int mid = (l+r)/2;
        if (node->left!=nullptr)
                query(node->left,l,mid);
        if (node->right!=nullptr)
                query(node->right,mid+1,r);
}

int main() {
        fin>>m;
        for (int i = 1;i<=m;++i) {
                fin>>op>>st>>dr;
                st+=c;
                dr+=c;
                if (op==1) {
                        // chirst arrival
                        // the answer becomes C variable
                        ans = 0;
                        query(root,1,n);
                        c = ans;
                        fout<<ans<<'\n';
                } else {
                        // paint
                        update(root,1,n);
                }
        }
        return 0;
}

• Subtask 1: 0 / 100