Submission #1238339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238339		bangan	Mosaic (IOI24_mosaic)	C++17	5 / 100	83 ms	16412 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 = (int)X.size();
    int q = (int)T.size();
    if (n==1) return vector<ll> (q, 0ll + X[0]);

    vector<ll> ans(q, 0), a;
    for (int i=1; i<n; i++) a.pb(X[i]);
    for (int i = n-2; 0<=i && i+1 < n-1; 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=0; i<q; i++) 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++) {
        for (int i=0; i<q; i++) {
            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;
}

• 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