Submission #1147428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147428		garam1732	모자이크 (IOI24_mosaic)	C++20	100 / 100	112 ms	23992 KiB

mosaic

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

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 100100*2;
const ll MOD = 998244353;
const ll INF = 2e9;

int r[3][MAXN], c[MAXN][3];
ll sum[2*MAXN][2];
int n, q;

ll solve(int x, int y) {
    if(x<0 || y<0) return 0;

    if(x<3) return r[x][y];
    if(y<3) return c[x][y];

    ll res = r[1][y]+c[x][1]-r[1][1];
    if(x<y) {
        res += (sum[y-x+n][0]-sum[0+n-1][0])*(x-1);
        res += (sum[-1+n][1]-sum[2-x+n-1][1])+(x-1)*(sum[-1+n][0]-sum[2-x+n-1][0]);
        res += (y-1)*(sum[y-2+n][0]-sum[y-x+n][0])-(sum[y-2+n][1]-sum[y-x+n][1]);
    } else {
        res += (sum[0+n][0]-sum[y-x+n-1][0])*(y-1);
        res += (sum[y-x-1+n][1]-sum[2-x+n-1][1])+(x-1)*(sum[y-x-1+n][0]-sum[2-x+n-1][0]);
        res += (y-1)*(sum[y-2+n][0]-sum[0+n][0])-(sum[y-2+n][1]-sum[0+n][1]);
    }

    return res;
}

vector<ll> res;
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) {

    while(X.size() < 5) X.push_back(0);
    while(Y.size() < 5) Y.push_back(0);

    n = X.size(), q = T.size();
    for(int i=0; i<n; i++) r[0][i] = X[i]; r[1][0] = Y[1], r[2][0] = Y[2];
    for(int i=1; i<=2; i++) for(int j=1; j<n; j++) r[i][j] = (!r[i][j-1])&&(!r[i-1][j]);
    for(int i=0; i<n; i++) c[i][0] = Y[i]; c[0][1] = X[1], c[0][2] = X[2];
    for(int i=1; i<=2; i++) for(int j=1; j<n; j++) c[j][i] = (!c[j][i-1])&&(!c[j-1][i]);

    sum[2-(n-1)+n][0] = c[n-1][2]; sum[2-(n-1)+n][1] = c[n-1][2]*(2-(n-1));
    for(int i=n-2; i>=2; i--) {
        sum[2-i+n][0] = sum[2-i+n-1][0]+c[i][2];
        sum[2-i+n][1] = sum[2-i+n-1][1]+c[i][2]*(2-i);
    }
    for(int i=3; i<n; i++) {
        sum[i-2+n][0] = sum[i-2+n-1][0]+r[2][i];
        sum[i-2+n][1] = sum[i-2+n-1][1]+r[2][i]*(i-2);
    }

    for(int i=0; i<3; i++) for(int j=0; j<n; j++) {
        if(i>0) r[i][j]+=r[i-1][j], c[j][i]+=c[j][i-1];
        if(j>0) r[i][j]+=r[i][j-1], c[j][i]+=c[j-1][i];
        if(i>0&&j>0) r[i][j]-=r[i-1][j-1], c[j][i]-=c[j-1][i-1];
    }

    for(int i=0; i<q; i++) {
        res.push_back(solve(B[i],R[i])-solve(B[i],L[i]-1)-solve(T[i]-1,R[i])+solve(T[i]-1,L[i]-1));
    }

    return res;
}

• 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