Submission #1106261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106261		vladilius	Painting Walls (APIO20_paint)	C++17	40 / 100	1562 ms	18772 KiB

paint

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int inf = 3e5;

struct ST{
    vector<int> t;
    int n;
    ST(int ns){
        n = ns;
        t.resize(4 * n);
    }
    void upd(int v, int tl, int tr, int& p, int& x){
        if (tl == tr){
            t[v] += x;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (p <= tm){
            upd(vv, tl, tm, p, x);
        }
        else {
            upd(vv + 1, tm + 1, tr, p, x);
        }
        t[v] = max(t[vv], t[vv + 1]);
    }
    void upd(int p, int x){
        p++;
        upd(1, 1, n, p, x);
    }
    int get(){
        return t[1];
    }
};

int minimumInstructions(int n, int m, int k, vector<int> x, vector<int> A, vector<vector<int>> B){
    vector<int> d[k];
    for (int i = 0; i < m; i++){
        for (int j: B[i]){
            d[j].pb(i);
        }
    }
    
    vector<int> p(n + 1);
    int i = 0, j = 0, j1 = 0; 
    ST T(inf);
    while (i < n){
        if (T.get() == (j1 - i)){
            j = j1;
            // [i, j1 - 1]
            while (j < n){
                for (int f: d[x[j]]){
                    T.upd(f - j + n, 1);
                    T.upd(f - j + (m + n), 1);
                }
                if (T.get() != (j - i + 1)){
                    j1++;
                    break;
                }
                j++; j1++;
            }
            
            if (i <= (j - m)){
                p[i]++;
                p[j - m + 1]--;
            }
        }
        
        for (int f: d[x[i]]){
            T.upd(f - i + n, -1);
            T.upd(f - i + (m + n), -1);
        }
        i++;
    }
    
    vector<bool> gd(n);
    int sum = 0;
    for (int i = 0; i < n; i++){
        sum += p[i];
        gd[i] = (sum > 0);
    }
    
    int mx = -1, t = -1, out = 0;
    for (int i = 0; i < n; i++){
        if (gd[i]) t = i;
        if (i == (mx + 1)){
            if (t == -1) return -1;
            mx = t + m - 1;
            t = -1;
            out++;
        }
    }
    return out;
}

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 37