제출 #1237805

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237805		bangan	모자이크 (IOI24_mosaic)	C++20	7 / 100	96 ms	17180 KiB

mosaic

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

#define ll long long

#define pb push_back

std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y, std::vector<int> T, std::vector<int> B, std::vector<int> lo, std::vector<int> hi) {
	int n = X.size();
	int q = (int)T.size();
    if (n==1) return vector<ll> (q, X[0]);

    vector<ll> ans(q);
    vector<int> all(q);
    iota(all.begin(), all.end(), 0);
    sort(all.begin(), all.end(), [&](int i, int j) {
        return B[i]<B[j];
    });
    // auto it = all.begin();
    // while (it!=all.end() && B[*it] < 2) it++;

    vector<ll> a;
    for (int i=1; i<n; i++) a.pb(X[i]);
    for (int i = n-2; 0<=i; i--) a[i] += a[i+1];

    auto get = [&](int l, int r) {
        if (r+1 == a.size()) return a[l];
        return a[l] - a[r+1];
    };

    {
        vector<ll> y;
        for (int t : Y) y.pb(t);
        for (int i=1; i<y.size(); i++) y[i] += y[i-1];
        for (int i : all) if (lo[i]==0) {
            ans[i] += y[B[i]];
            if (0 <= T[i]-1) ans[i] -= y[T[i]-1];
            lo[i]++;
        }
    }

    for (int r=0; r<2; r++) {
        // while (it!=all.end() && T[*it]==r) {
        //     int L = lo[*it];
        //     int R = hi[*it];
        //     if (L==0) ans[*it] = Y[r], L++;
        //     L--, R--;
        //     if (L<=R) ans[*it] += get(L, R);
        //     it++;
        // }
        for (int i : all) {
            if (r==T[i] && T[i]<=B[i] && lo[i]<=hi[i]) {
                T[i]++;
                int L = lo[i];
                int R = hi[i];
                L--, R--;
                ans[i] += get(L, R);
            }
        }

        if (r+1 != n) {
            vector<ll> b;
            b.pb((Y[r+1]|get(0, 0))^1);
            for (int i=1; i<a.size(); i++) b.pb((b.back()|get(i, i))^1);
            swap(a, b);
            for (int i = n-2; 0<=i; i--) a[i] += a[i+1];
        }
    }
    return ans;

    // {
    //     vector<ll> b = a;
    //     a.clear();
    //     for (int i=0; i<n; i++) a.pb(0);
    //     for (int i:b) a.pb(i);
    // }
    // vector<ll> b;
    // {
    //     vector<ll> t = a;
    //     for (int i = n-2; 0<=i; i--) t[i] += t[i+1];
    //     for (int i=0; i<n; i++) b.pb(0);
    //     for (int i:t) b.pb(i);
    // }
    // int z=n;
    // vector<ll> pre = {a[z]};

    // auto get_one = [&](int i, int c) -> ll {
    //     int l = i;
    //     int r = i+c;
    //     // assert(a.size()<=r);
    //     if (a.size() <= r) return b[l];
    //     return b[l]-b[r];
    // };

    // auto GET = [&](int l, int r, int c) -> ll {
    //     if (a.size() <= r+1) return get_one(l, c);
    //     return get_one(l, c) - get_one(r+1, c);
    // };

    // for (int r=2; r<n; r++) {
    //     while (it!=all.end() && B[*it]==r) {
    //         int L = lo[*it];
    //         int R = hi[*it];
    //         int U = T[*it];
    //         int D = B[*it];
    //         if (R==0) {
    //             it++;
    //             continue;
    //         }
    //         L--; R--;
    //         if (L==0) {
    //             ans[*it] += pre.back();
    //             if (0 <= U-3) ans[*it] -= pre[U-3];
    //             L++;
    //         }
    //         if (L<=R) ans[*it] += GET(z+L, z+R, D-U+1);
    //         it++;
    //     }
        
    //     if (r+1 != n) {
    //         z--;
    //         int t = (Y[r+1]|get(z+1, z+1))^1;
    //         if (z+2 < a.size()) {
    //             a[z+1] = ((get(z+2, z+2)|t) ^ 1) + a[z+2];
    //             b[z+1] = b[z+2] + a[z+1];
    //         }
    //         a[z] = t + a[z+1];
    //         b[z] = a[z] + b[z+1];
    //         pre.pb(pre.back() + a[z]);
    //     }
    // }
    // return ans;
}

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