Submission #1160074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160074		Andrey	Mosaic (IOI24_mosaic)	C++20	100 / 100	97 ms	34888 KiB

mosaic

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

vector<long long> wow(500001);
vector<long long> wut(500001);
long long pr1[4][200001];
long long pr2[200001][4];

long long calc(long long l, long long r, long long d) {
    long long ans = 0;
    ans+=wut[l+d-1]-wut[l-1];
    ans-=(wow[l+d-1]-wow[l-1])*(l-1);
    ans-=wut[r]-wut[r-d];
    ans+=(wow[r]-wow[r-d])*(r+1);
    ans+=(wow[r-d]-wow[l+d-1])*d;
    return ans;
}

std::vector<long long> mosaic(std::vector<int> x, std::vector<int> y,
                              std::vector<int> t, std::vector<int> B,
                              std::vector<int> l, std::vector<int> r) {
    long long n = x.size();
    long long q = t.size();
    for(long long i = 0; i < 4; i++) {
        for(long long j = 0; j < n+1; j++) {
            pr1[i][j] = 0;
            pr2[j][i] = 0;
        }
    }
    for(long long i = 1; i <= n; i++) {
        pr1[1][i] = x[i-1];
        if(i <= 3) {
            pr2[1][i] = x[i-1];
        }
        pr2[i][1] = y[i-1];
        if(i <= 3) {
            pr1[i][1] = y[i-1];
        }
    }
    for(long long i = 2; i <= 3; i++) {
        for(long long j = 2; j <= n; j++) {
            if(pr1[i][j-1] == 0 && pr1[i-1][j] == 0) {
                pr1[i][j] = 1;
            }
            if(pr2[j-1][i] == 0 && pr2[j][i-1] == 0) {
                pr2[j][i] = 1;
            }
        }
    }
    vector<long long> troll(2*n+1);
    for(long long i = 3; i <= n; i++) {
        troll[3-i+n] = pr1[3][i];
        troll[i-3+n] = pr2[i][3];
    }
    for(long long i = 1; i <= 2*n; i++) {
        wow[i] = wow[i-1]+troll[i];
        wut[i]+=wut[i-1]+troll[i]*i;
    }
    for(long long i = 1; i <= 3; i++) {
        for(long long j = 1; j <= n; j++) {
            pr1[i][j]+=pr1[i-1][j]+pr1[i][j-1]-pr1[i-1][j-1];
            pr2[j][i]+=pr2[j-1][i]+pr2[j][i-1]-pr2[j-1][i-1];
        }
    }
    vector<long long> answer(q);
    for(long long i = 0; i < q; i++) {
        long long a = t[i]+1,b = B[i]+1,c = l[i]+1,d = r[i]+1;
        long long ans = 0;
        if(a <= 2) {
            long long x = min(2LL,b);
            ans+=pr1[x][d]-pr1[a-1][d]-pr1[x][c-1]+pr1[a-1][c-1];
            a = x+1;
        }
        if(c <= 2 && a <= b) {
            long long x = min(2LL,d);
            ans+=pr2[b][x]-pr2[a-1][x]-pr2[b][c-1]+pr2[a-1][c-1];
            c = x+1;
        }
        if(a <= b && c <= d) {
            ans+=calc(a-d+n,b-c+n,min(b-a+1,d-c+1));
        }
        answer[i] = ans;
    }
    return answer;
}

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