Submission #820108

#	Time	Username	Problem	Language	Result	Execution time	Memory
820108		Ahmed57	Land of the Rainbow Gold (APIO17_rainbow)	C++17	0 / 100	295 ms	219792 KiB

rainbow

#include <bits/stdc++.h>

using namespace std;
#define M ((L+R)/2)
const int MAXN = 200001;
const int SIZE = (6e5+9)*19+1;

struct pres{
set<int> s[MAXN+5];
void add(int x,int y){
    s[x].insert(y);
}
int root[MAXN+5];
void bld(){
    root[1] = build();
    for(int i = 1;i<=MAXN;i++){
        root[i+1] = root[i];
        for(auto j:s[i]){
            root[i+1] = update(j,root[i+1]);
        }
    }
}
int qry(int l,int r,int L,int R){
    if(r>R)return 0;
    return query(r,R,root[L+1])-(l?query(r,R,root[l]):0);
}
int l[SIZE], r[SIZE], st[SIZE], NODES = 0;
int n;
int newleaf(int value) {
    int p = ++NODES;
    l[p] = r[p] = 0; // null
    st[p] = value;
    return p;
}
int newparent(int lef, int rig) {
    int p = ++NODES;
    l[p] = lef;
    r[p] = rig;
    st[p] = st[lef] + st[rig]; // immediately update value from children
    return p;
}
int update(int i,int p, int L=1, int R=MAXN) {
    if (L == R)return newleaf(st[p]+1);
    if (i <= M)return newparent(update(i,l[p], L, M), r[p]);
    else return newparent(l[p], update(i,r[p], M + 1, R));
}
int build(int L=1, int R=MAXN) {
    if (L == R) return newleaf(0); // construct as leaf
    else return newparent(build(L, M),build(M+1,R)); // construct as parent
}
int query(int lq,int rq,int p,int L = 1,int R = MAXN){
    if(L>=lq&&R<=rq)return st[p];
    if(L>rq||R<lq)return 0;
    return query(lq,rq,l[p],L,M)+query(lq,rq,r[p],M+1,R);
}
}ver,edgehorz,edgevert,rivers;
void add_river(int x,int y){
    rivers.add(x,y);
    ver.add(x,y);
    ver.add(x+1,y);
    ver.add(x,y+1);
    ver.add(x+1,y+1);
    edgehorz.add(x,y);
    edgehorz.add(x+1,y);
    edgevert.add(x,y);
    edgevert.add(x,y+1);
}
int mxr ,mnr,mxc,mnc;
void init(int R, int C, int sr, int sc, int MM, char *S) {
    add_river(sr,sc);
    mxr = sr,mnr = sr,mxc = sc,mnc = sc;
    for(int i = 0;i<MM;i++){
        if(S[i]=='N')sr--;
        if(S[i]=='S')sr++;
        if(S[i]=='W')sc--;
        if(S[i]=='E')sc++;
        add_river(sr,sc);
        mxr = max(mxr,sr);
        mnr = min(mnr,sr);
        mxc = max(mxc,sc);
        mnc = min(mnc,sc);
    }
    rivers.bld();ver.bld();
    edgehorz.bld();edgevert.bld();
}
int colour(int ar, int ac, int br, int bc) {
    int E = edgehorz.qry(ar + 1, br, ac, bc) + edgevert.qry(ar, br, ac + 1, bc);
    int V = ver.qry(ar + 1, br, ac + 1, bc);
    int R = rivers.qry(ar, br, ac, bc);
    int C = (ar >= mnr || br <= mxr || ac >= mnc || bc <= mxc ? 1 : 2);
    return E - V + C - R;
}/*
int main(){
    init(6, 4,
3, 3, 9,
"NWESSWEWS");
cout<<colour(3,2,4,4);
}
*/

• Subtask 1: 0 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26