Submission #1305650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305650		aaaaaaaa	Watering can (POI13_kon)	C++20	0 / 100	189 ms	196608 KiB

kon

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

#define all(x) x.begin(), x.end()

const int mxN = 2005;

struct state{
    deque<int> ar;
    int ans, lz, cnt;
    state(){
        ans = lz = cnt = 0;
    }
} seg[mxN * 4];

int N, K, t[mxN];

struct mst{
    void build(int node, int start, int end){
        if(start == end){
            if(t[start] >= K) seg[node].ans = 1;
            else seg[node].ar = {K - t[start]};
            return;
        }
        int mid = start + (end - start) / 2;
        build(node * 2 + 1, start, mid);
        build(node * 2 + 2, mid + 1, end);
        merge(all(seg[node * 2 + 1].ar), all(seg[node * 2 + 2].ar), back_inserter(seg[node].ar));
        seg[node].ans = seg[node * 2 + 1].ans + seg[node * 2 + 2].ans;
    }
    void push(int node, int start, int end){
        if(seg[node].lz == 0) return;
        seg[node].cnt += seg[node].lz;
        while((int) seg[node].ar.size() && seg[node].cnt >= seg[node].ar[0]) seg[node].ar.pop_front(), seg[node].ans += 1;
        if(start ^ end){
            seg[node * 2 + 1].lz += seg[node].lz;
            seg[node * 2 + 2].lz += seg[node].lz;
        }
        seg[node].lz = 0;
    }
    void update(int node, int start, int end, int l, int r){
        if(start > r || end < l) return;
        push(node, start, end);
        if(start >= l && end <= r){
            seg[node].lz = 1;
            push(node, start, end);
            return;
        }
        int mid = start + (end - start) / 2;
        update(node * 2 + 1, start, mid, l, r);
        update(node * 2 + 2, mid + 1, end, l, r);
        merge(all(seg[node * 2 + 1].ar), all(seg[node * 2 + 2].ar), back_inserter(seg[node].ar));
        seg[node].ans = seg[node * 2 + 1].ans + seg[node * 2 + 2].ans;
    }
    int query(int node, int start, int end, int l, int r){
        push(node, start, end);
        if(start > r || end < l) return 0;
        if(start >= l && end <= r) return seg[node].ans;
        int mid = start + (end - start) / 2;
        int left = query(node * 2 + 1, start, mid, l, r);
        int right = query(node * 2 + 2, mid + 1, end, l, r);
        return left + right;
    }
    int query(int l, int r){
        return query(0, 0, N - 1, l, r);
    }
    void update(int l, int r){
        update(0, 0, N - 1, l, r);
    }
} mst;

void inicjuj(int n, int k, int *D)
{
    N = n, K = k;
    for(int i = 0; i < n; ++i) t[i] = D[i];
    mst.build(0, 0, n - 1);
}

void podlej(int a, int b)
{
    mst.update(a, b);
}

int dojrzale(int a, int b)
{
    return mst.query(a, b);
}

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