Submission #1211086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211086		Aviansh	Mosaic (IOI24_mosaic)	C++20	5 / 100	213 ms	67392 KiB

mosaic

#include "mosaic.h"

#include <bits/stdc++.h>

using namespace std;

struct segTree{
    long long *st;
    int n;
    segTree(int siz){
        int x=  ceil(log2(siz));
        x++;
        n=siz-1;
        st=new long long[(1<<x)];
        fill(st,st+(1<<x),0);
    }
    void rupdate(int l, int r, int ind, int i, int val){
        if(i<l||i>r)
            return;
        if(l==r){
            st[ind]=val;
            return;
        }
        int mid = (l+r)/2;
        rupdate(l,mid,ind*2+1,i,val);
        rupdate(mid+1,r,ind*2+2,i,val);
        st[ind]=st[ind*2+1]+st[ind*2+2];
    }
    void update(int i, int val){
        rupdate(0,n,0,i,val);
    }

    long long rquery(int l, int r, int s, int e, int ind){
        if(e<l||s>r)
            return 0;
        if(s<=l&&r<=e){
            return st[ind];
        }
        int mid = (l+r)/2;
        return rquery(l,mid,s,e,ind*2+1)+rquery(mid+1,r,s,e,ind*2+2);
    }

    long long query(int l, int r){
        if(l>r)
            return 0;
        return rquery(0,n,l,r,0);
    }
};

vector<long long> mosaic(vector<int> X, vector<int> Y,vector<int> T, vector<int> B,vector<int> L, vector<int> R) {
    int n = X.size();
    int q = (int)T.size();
    if(n==1){
        vector<long long>ans(q,X[0]);
        return ans;
    }
    else if(n==2){
        int rem = 0;
        if(X[1]==Y[1]&&X[1]==0){
            rem=1;
        }
        vector<long long>ans(q);
        for(int i = 0;i<q;i++){
            //later
            if(T[i]==0){
                if(L[i]==0){
                    ans[i]+=X[0];
                }
                if(R[i]==1){
                    ans[i]+=X[1];
                }
            }
            if(B[i]==1){
                if(L[i]==0){
                    ans[i]+=Y[1];
                }
                if(R[i]==1){
                    ans[i]+=rem;
                }
            }
        }
        return ans;
    }
    //X is row top
    vector<long long>nxc1(n-1);
    vector<long long>nxc2(n-2);
    vector<long long>nxr1(n-1);
    vector<long long>nxr2(n-2);
    nxc1[0]=nxr1[0]=((bool)(X[1]==0&&Y[1]==0));
    for(int i = 1;i<n-1;i++){
        nxc1[i]=(nxc1[i-1]==0&&Y[i+1]==0);
        nxr1[i]=(nxr1[i-1]==0&&X[i+1]==0);
    }
    nxc2[0]=nxr2[0]=((bool)(nxc1[1]==0&&nxr1[1]==0));

    for(int i = 1;i<n-2;i++){
        nxc2[i]=(nxc2[i-1]==0&&nxc1[i+1]==0);
        nxr2[i]=(nxr2[i-1]==0&&nxr1[i+1]==0);
    }
    int off = n+5;
    segTree up(3*n);
    segTree flat(3*n);
    segTree down(3*n);
    for(int i = 0;i<n-2;i++){
        if(nxc1[i]){
            int k = 2-(2+i);
            int offd = k+off;
            //cout << "adding1: " << k << "\n";
            //cout << "offd: " << offd << "\n";
            up.update(offd,offd);
            flat.update(offd,1);
            down.update(offd,-offd);
        }
        if(nxr1[i]){
            int k = (i+2)-2;
            int offd = k+off;
            //cout << "adding2: " << k << "\n";
            //cout << "offd: " << offd << "\n";
            up.update(offd,offd);
            flat.update(offd,1);
            down.update(offd,-offd);
        }
    }
    for(int i = 1;i<n;i++){
        X[i]+=X[i-1];
        Y[i]+=Y[i-1];
    }
    for(int i = 1;i<n-1;i++){
        nxc1[i]+=nxc1[i-1];
        nxr1[i]+=nxr1[i-1];
    }
    for(int i = 1;i<n-2;i++){
        nxc2[i]+=nxc2[i-1];
        nxr2[i]+=nxr2[i-1];
    }
    //segs made
    vector<long long>ans(q);
    for(int i = 0;i<q;i++){
        long long curr=0;
        int t,bo,l,r;
        bo=T[i];
        t=B[i];
        l=L[i];
        r=R[i];

        //external:

        if(bo<2){
            if(r-1>=0)
                curr+=nxr1[r-1];
            if(l-2>=0)
                curr-=nxr1[l-2];
            if(bo<1){
                if(r>=0)
                    curr+=X[r];
                if(l-1>=0)
                    curr-=X[l-1];
            }
        }
        //cout << "part1: " << curr << "\n";
        if(l<2){
            if(t-1>=0){
                curr+=nxc1[t-1];
                curr-=nxc1[max(0,bo-2)];
            }
            //cout << "part2.1: " << curr << "\n";
            if(l<1){
                if(t>=0){
                    curr+=Y[t];
                    curr-=Y[max(0,bo-1)];
                }
            }
        }


        //within range:
        bo=max(2,bo);
        l=max(2,l);
        if(r<l||t<bo){
            ans[i]=curr;
            continue;
        }
        //cout << "coords: " << l << " " << r << " " << bo << " " << t << "\n";
        int a = l-t+off;
        int b = min(r-t,l-bo)+off;
        int c = max(r-t,l-bo)+off;
        int d = r-bo+off;

        if(c<b){
            //swap(c,b);
            assert(0);
        }

        //cout << a << " " << b << " " << c << " " << d << "\n";
        //cout << "pre: " << curr << "\n";
        curr+=up.query(a,b)-flat.query(a,b)*(a-1);
        //cout << "here1: " << curr << "\n";
        curr+=flat.query(b+1,c)*(min(r-l+1,t-bo+1));
        //cout << "here2: " << curr << "\n";
        curr+=-down.query(c+1,d)-(1LL*(c)*flat.query(c+1,d));
        //cout << "segs: " << curr << "\n";

        //cout << bo << " " << t  << " " << l << " " << r << " " << curr << "\n";
        ans[i]=curr;
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 8
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22