Submission #1211108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211108		Aviansh	Mosaic (IOI24_mosaic)	C++20	53 / 100	311 ms	75284 KiB

mosaic

#include "mosaic.h"

#include <bits/stdc++.h>

using namespace std;

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

    long long rquery(long long l, long long r, long long s, long long e, long long ind){
        if(e<l||s>r)
            return 0;
        if(s<=l&&r<=e){
            return st[ind];
        }
        long long 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(long long l, long long 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) {
    long long n = X.size();
    long long q = (long long)T.size();
    if(n==1){
        vector<long long>ans(q,X[0]);
        return ans;
    }
    else if(n==2){
        long long rem = 0;
        if(X[1]==Y[1]&&X[1]==0){
            rem=1;
        }
        vector<long long>ans(q);
        for(long long 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(long long i = 1;i<n-1;i++){
        nxc1[i]=((bool)nxc1[i-1]==0&&Y[i+1]==0);
        nxr1[i]=((bool)nxr1[i-1]==0&&X[i+1]==0);
    }
    nxc2[0]=nxr2[0]=((bool)(nxc1[1]==0&&nxr1[1]==0));

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

        if(bo<2){
            if(t>=1){
                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(r>=1){
                if(t-1>=0){
                    curr+=nxc1[t-1];
                    curr-=nxc1[max(0LL,bo-2)];
                }
            }
            //cout << "part2.1: " << curr << "\n";
            if(l<1){
                if(t>=0){
                    curr+=Y[t];
                    curr-=Y[max(0LL,bo-1)];
                }
            }
        }


        //within range:
        bo=max(2LL,bo);
        l=max(2LL,l);
        if(r<l||t<bo){
            ans[i]=curr;
            continue;
        }
        //cout << "coords: " << l << " " << r << " " << bo << " " << t << "\n";
        long long a = l-t+off;
        long long b = min(r-t,l-bo)+off;
        long long c = max(r-t,l-bo)+off;
        long long 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: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 8
• Subtask 6: 22 / 22
• Subtask 7: 19 / 19
• Subtask 8: 0 / 22