Submission #329660

#	Time	Username	Problem	Language	Result	Execution time	Memory
329660		gmyu	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	551 ms	87280 KiB

apple

/*
ID: USACO_template
LANG: C++
PROG: USACO
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define fst first
#define snd second
#define pb  push_back
#define trav(u, adj_v) for (auto& u: adj_v)

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 100007
#define MAXE 100007

const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
    int x, y;
    int val;
    int visited;
};
struct EDGE {
    int from, to;
    ll weight;
    bool operator<(EDGE other) const { return weight < other.weight; }
};

/// code from USACO examples
void setIO(string name) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen((name+".in").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
}
bool debug = false, submit = true;

int Q;

/// ------ Segment Treee --------
int Nseg[2];
int vct;
struct SEGNODE {
    int lpt, rpt;
    int sum;                 /// sum is always updated before lazy value is used.
    bool LazyPushedDown;    /// flag whether we already pushed down the lazy additional value
};
SEGNODE seg[6000007];    /// max 2e5 unique y, which needs 2^19 for Nseg

void newSegNode(int v) {
    seg[v].lpt = -1; seg[v].rpt = -1;
    seg[v].sum = 0;
    seg[v].LazyPushedDown = true;
}
void initSeg() {
    /// build a segment tree for array of interest indexed from Nseg[0] to Nseg[1]
    Nseg[0] = 1;
    Nseg[1] = 1e9;
    vct = 1;
    newSegNode(vct);
}
void pullUp(int v, int l, int m, int r) {
    if(l==r) return;

    int ans1 = (seg[v].lpt == -1) ? 0 : seg[seg[v].lpt].sum;
    int ans2 = (seg[v].rpt == -1) ? 0 : seg[seg[v].rpt].sum;
    seg[v].sum = ans1 + ans2;
}
void pushDown(int v, int l, int m, int r) {

    if(l==r) {
        seg[v].LazyPushedDown = true;
        return;
    }

    if(seg[v].LazyPushedDown) return;

    /// push down
    int v1 = seg[v].lpt, v2 = seg[v].rpt;

    if(v1 == -1) {
        vct++; newSegNode(vct);
        seg[v].lpt = vct;
        v1 = vct;
    }
    seg[v1].sum = (m - l + 1);
    seg[v1].LazyPushedDown = false;

    if(v2 == -1) {
        vct++; newSegNode(vct);
        seg[v].rpt = vct;
        v2 = vct;
    }
    seg[v2].sum = (r - (m+1) + 1);
    seg[v2].LazyPushedDown = false;

    /// update v
    seg[v].LazyPushedDown = true;
}
ll querySeg(int qle, int qri, int v = 1, int l = Nseg[0], int r = Nseg[1]) {
    if(r < qle || l > qri) return 0;
    if(qle <= l && r <= qri) {
        return seg[v].sum;
    }

    int mid = (l + r) / 2;
    pushDown(v, l, mid, r);

    int ans1 = 0, ans2 = 0;

    if(qle <= mid) {
        if(seg[v].lpt == -1) {
            ans1 = 0;
        } else {
            ans1 = querySeg(qle, qri, seg[v].lpt, l, mid);
        }
    }

    if(qri >= mid+1) {
        if(seg[v].rpt == -1) {
            ans2 = 0;
        } else {
            ans2 = querySeg(qle, qri, seg[v].rpt, mid+1, r);
        }
    }

    pullUp(v, l, mid, r);

    return ans1 + ans2;
}
void updateSeg(int ule, int uri, int v = 1, int l = Nseg[0], int r = Nseg[1]){
    if(r < ule || l > uri) return;

    int mid = (l + r) / 2;
    if(ule <= l && r <= uri) {
        pushDown(v, l, mid, r);

        seg[v].sum = (r - l + 1);
        seg[v].LazyPushedDown = false;

        return;
    }

    pushDown(v, l, mid, r);

    if(ule <= mid) {
        if(seg[v].lpt == -1) {
            vct++; newSegNode(vct);
            seg[v].lpt = vct;
        }
        if(debug) cout << " .. go left {" << l << "," << mid << "}" << endl;
        updateSeg(ule, uri, seg[v].lpt, l, mid);
    }

    if(uri >= mid+1) {
        if(seg[v].rpt == -1) {
            vct++; newSegNode(vct);
            seg[v].rpt = vct;
        }
        if(debug) cout << " .. go right {" << mid+1 << "," << r << "}" << endl;
        updateSeg(ule, uri, seg[v].rpt, mid+1, r);
    }

    pullUp(v, l, mid, r);
}


int main() {
    debug = false; submit = false;
    if(submit) setIO("testName");

    int i, j, k;
    int c = 0;

    cin >> Q ;

    initSeg();

    for(i=0; i<Q; i++) {
        int cmd, a, b;
        cin >> cmd >> a >> b;
        if(cmd == 2) {
            updateSeg(a+c, b+c);
        } else {
            c = querySeg(a+c, b+c);
            cout << c << endl;
        }
    }

}

Compilation message (stderr)

apple.cpp: In function 'int main()':
apple.cpp:191:12: warning: unused variable 'j' [-Wunused-variable]
  191 |     int i, j, k;
      |            ^
apple.cpp:191:15: warning: unused variable 'k' [-Wunused-variable]
  191 |     int i, j, k;
      |               ^
apple.cpp: In function 'void setIO(std::string)':
apple.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   52 |     freopen((name+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:53:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   53 |     freopen((name+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100