Submission #1263276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263276		damoon	Land of the Rainbow Gold (APIO17_rainbow)	C++20	12 / 100	951 ms	613444 KiB

rainbow

#include<bits/stdc++.h>
using namespace std;

#define ll long long

#define pb push_back
#define all(x) x.begin(),x.end()
#define unicorn(x) x.resize(unique(all(x))-x.begin())

typedef pair<int,int> pii;
#define f first
#define s second

string pr(vector<pii> vv){for(auto [x,y]:vv)cout<<"("<<x<<","<<y<<") ";return"";}
string pr(vector<int> vv){for(auto i:vv)cout<<i<<" ";return"";}

const int L=2e5+10, inf=1e9+10;
int MA;
int xmx=-inf, xmn=inf, ymx=-inf, ymn=inf;
vector<pii> P;

struct RC{
    struct node{
        int l,r,mid,sum;
        node* lc;
        node* rc;

        node(int l2, int r2){
            l = l2;
            r = r2;
            lc = nullptr;
            rc = nullptr;
            mid = (l+r)/2;
            sum = 0;
        }

        void spread(){
            if(lc == nullptr){
                lc = new node(l,mid);
                rc = new node(mid,r);
            }
        }

        void update(int ind,int x,node* newnode){
            if(l+1 == r){
                newnode->sum = sum;
                newnode->sum += x;
                return;
            }
            spread();
            if(ind < mid){
                newnode->rc = rc;
                newnode->lc = new node(l,mid);
                lc->update(ind,x,newnode->lc);
            }
            else{
                newnode->lc = lc;
                newnode->rc = new node(mid,r);
                rc->update(ind,x,newnode->rc);
            }
            newnode->sum = newnode->lc->sum + newnode->rc->sum;
        }

        int get(int l2,int r2){
            if(l==l2 and r==r2)
                return sum;
            int ans = 0;
            spread();
            if(l2 < mid)
                ans += lc->get(l2,min(r2,mid));
            if(r2 > mid)
                ans += rc->get(max(l2,mid),r2);
            return ans;
        }
    };

    node* R[L];
    vector<int> good[L];
    void add(int x,int y){
        if(x and y)
            good[x].pb(y);
    }

    void build(){
        R[L-1] = new node(1,L);
        for(int i=L-2;i>=1;i--){
            R[i] = R[i+1];
            sort(all(good[i]));
            unicorn(good[i]);
            for(auto x:good[i]){
                node* rt = new node(1,L);
                R[i]->update(x,1,rt);
                R[i] = rt;
            }
        }
    }

    int get(int x,int y){
        return R[x]->get(y,L);
    }
}oo,ot,to,tt;

void init(int A,int B,int sx,int sy,int N,char* S){
    P.pb(pii(sx,sy));
    for(int i=0;i<N;i++){
        char c = S[i];
        if(c == 'N')
            sx--;
        if(c == 'S')
            sx++;
        if(c == 'W')
            sy--;
        if(c == 'E')
            sy++;
        P.pb(pii(sx,sy));
    }

    sort(all(P));
    unicorn(P);

    map<pii,bool> is;
    for(auto [x,y]:P){
        //oo
        oo.add(x,y);

        //ot
        ot.add(x,y);
        ot.add(x,y-1);

        //to
        to.add(x,y);
        to.add(x-1,y);

        //tt
        tt.add(x,y);
        tt.add(x-1,y);
        tt.add(x,y-1);
        tt.add(x-1,y-1);

        is[pii(x,y)] = 1;
        xmx = max(xmx , x);
        ymx = max(ymx , y);
        xmn = min(xmn , x);
        ymn = min(ymn , y);
    }

    oo.build();
    ot.build();
    to.build();
    tt.build();

    if(xmx!=A and xmn!=1 and ymx!=B and ymn!=1){
        MA = 0;
        for(auto [x,y]:P){
            for(int xd=-1;xd<=1;xd++){
                for(int yd=-1;yd<=1;yd++){
                    if(xd !=0 or yd != 0){
                        MA += is[pii(x+xd,y+yd)];
                    }
                }
            }
        }
        MA /= 2;
        MA = MA - P.size() + 2;
        for(auto [x,y]:P){
            MA -= (is[pii(x,y+1)] and is[pii(x+1,y+1)]);
            MA -= (is[pii(x,y+1)] and is[pii(x+1,y)]);
            MA -= (is[pii(x+1,y)] and is[pii(x+1,y+1)]);
            MA -= (is[pii(x+1,y)] and is[pii(x+1,y-1)]);
        }
    }

    /*
    cout<<"P: "<<pr(P)<<endl;
    for(int i=1;i<=A;i++){
        cout<<"good["<<i<<"]: "<<pr(ot.good[i])<<endl;
    }
    */
}

ll get(int x1,int y1,int x2,int y2, RC &X){
    if(x2 <= x1 or y2 <= y1)
        return 0;
    ll ans = (x2-x1)*(y2-y1);
    ans -= X.get(x1,y1);
    ans -= X.get(x2,y2);
    ans += X.get(x1,y2);
    ans += X.get(x2,y1);
    return ans;
}

int colour(int x1,int y1,int x2,int y2){
    if(x1<xmn and x2>xmx and y1<ymn and y2>ymx)
        return MA;
    x2++;
    y2++;
    //cout<<"oo: "<<get(x1,y1,x2,y2,oo)<<" / ot: "<<get(x1,y1,x2,y2-1,ot)<<" / to: "<<get(x1,y1,x2-1,y2,to)<<" / tt: "<<get(x1,y1,x2-1,y2-1,tt)<<endl;
    return get(x1,y1,x2,y2,oo) - get(x1,y1,x2,y2-1,ot) - get(x1,y1,x2-1,y2,to) + get(x1,y1,x2-1,y2-1,tt);
}

/*
int main(){

    ifstream cin ("input.txt");

    int X,Y,sx,sy,N,q;
    string inp;
    char I[100];
    cin>>X>>Y>>N>>q;
    cin>>sx>>sy;
    if(N)
        cin>>inp;
    for(int i=0;i<N;i++){
        I[i] = inp[i];
    }
    init(X,Y,sx,sy,N,I);

    for(int i=1;i<=q;i++){
        int x1,x2,y1,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout<<colour(x1,y1,x2,y2)<<endl;
    }
}
*/

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