Submission #1187066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187066		Zbyszek99	Mosaic (IOI24_mosaic)	C++20	100 / 100	105 ms	45136 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

ll arr1[4][200'001];
ll pref1[4][200'001];
ll arr2[200'001][4];
ll pref2[200'001][4];

ll deg_pref[500'001];
ll deg_pref_plus[500'001];
ll deg_pref_minus[500'001];
const int deg_add = 200'003;

vl mosaic(vi X, vi Y, vi T, vi B, vi L, vi R) 
{
    int n = siz(X);
    rep2(i,1,n) arr1[1][i] = X[i-1];
    rep2(i,1,n) arr2[i][1] = Y[i-1];
    rep2(i,1,min(3,n)) arr1[i][1] = Y[i-1];
    rep2(i,1,min(3,n)) arr2[1][i] = X[i-1];
    rep2(y,2,3) rep2(x,2,n)
    {
        if(arr1[y-1][x] == 0 && arr1[y][x-1] == 0)
        {
            arr1[y][x] = 1;
        }
        else
        {
            arr1[y][x] = 0;
        }
    }
    rep2(x,2,3) rep2(y,2,n) 
    {
        if(arr2[y-1][x] == 0 && arr2[y][x-1] == 0)
        {
            arr2[y][x] = 1;
        }
        else
        {
            arr2[y][x] = 0;
        }
    }
    rep2(y,1,3)
    {
        rep2(x,1,n)
        {
            pref1[y][x] = pref1[y][x-1] + arr1[y][x]; 
        }
    }
    rep2(x,1,3)
    {
        rep2(y,1,n)
        {
            pref2[y][x] = pref2[y-1][x] + arr2[y][x]; 
        }
    }
    rep2(y,3,200'000)
    {
        deg_pref[3-y+deg_add] = arr2[y][3];
        deg_pref_plus[3-y+deg_add] = arr2[y][3] * (3-y+deg_add);
        deg_pref_minus[3-y+deg_add] = arr2[y][3] * (500'000 - (3-y+deg_add));
    }
    rep2(x,3,200'000)
    {
        deg_pref[x-3+deg_add] = arr1[3][x];
        deg_pref_plus[x-3+deg_add] = arr1[3][x] * (x-3+deg_add);
        deg_pref_minus[x-3+deg_add] = arr1[3][x] * (500'000 - (x-3+deg_add));
    }
    rep2(i,1,500'000)
    {
        deg_pref[i] += deg_pref[i-1];
        deg_pref_plus[i] += deg_pref_plus[i-1];
        deg_pref_minus[i] += deg_pref_minus[i-1];
    }
    int q = siz(T);
    vl anses(q,0);
    rep(qq,q)
    {
        int y1 = T[qq]+1;
        int y2 = B[qq]+1;
        int x1 = L[qq]+1;
        int x2 = R[qq]+1;
        while(y1 <= 3 && y1 <= y2)
        {
            anses[qq] += pref1[y1][x2] - pref1[y1][x1-1];
            y1++;
        }
      //  cout << anses[qq] << " " << x1 << " " << x2 << " " << y1 << " " << y2 << " xd1\n";
        if(y1 > y2) continue;
        while(x1 <= 3 && x1 <= x2)
        {
            anses[qq] += pref2[y2][x1] - pref2[y1-1][x1];
            x1++;
        } 
       // cout << anses[qq] << " " << x1 << " " << x2 << " " << y1 << " " << y2 << " xd2\n";
        if(x1 > x2) continue;
        int start_deg = x1-y2+deg_add;
        int end_deg = x2-y1+deg_add;
      //  cout << start_deg << " " << end_deg << " " << deg_pref[start_deg] - deg_pref[start_deg-1] << " " << deg_pref[end_deg] - deg_pref[end_deg-1] << " degs\n";
        if(x2-x1 >= y2-y1)
        {
            anses[qq] += (deg_pref_plus[start_deg + (y2-y1)-1] - deg_pref_plus[start_deg-1]) - (deg_pref[start_deg + (y2-y1)-1] - deg_pref[start_deg-1]) * (start_deg-1);
            start_deg += (y2-y1);
            anses[qq] += (deg_pref_minus[end_deg] - deg_pref_minus[end_deg - (y2-y1)]) - ((deg_pref[end_deg] - deg_pref[end_deg - (y2-y1)])) * (500'000-end_deg-1);
            end_deg -= (y2-y1);
            anses[qq] += (deg_pref[end_deg] - deg_pref[start_deg-1]) * (y2-y1+1);
        }
        else
        {
            anses[qq] += (deg_pref_plus[start_deg + (x2-x1)-1] - deg_pref_plus[start_deg-1]) - (deg_pref[start_deg + (x2-x1)-1] - deg_pref[start_deg-1]) * (start_deg-1);
            start_deg += (x2-x1);
            anses[qq] += (deg_pref_minus[end_deg] - deg_pref_minus[end_deg - (x2-x1)]) - ((deg_pref[end_deg] - deg_pref[end_deg - (x2-x1)])) * (500'000-end_deg-1);
            end_deg -= (x2-x1);
            anses[qq] += (deg_pref[end_deg] - deg_pref[start_deg-1]) * (x2-x1+1);
        }
    }
    return anses;
}  

• 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