oj.uz

Submission #298976

# Submission time Handle Problem Language Result Execution time Memory
298976 2020-09-14T11:29:35 Z mat_v Watering can (POI13_kon) C++14
0 / 100
 4000 ms 11132 KB 
#include "koninc.h"
#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define maxn 300005
#define pii pair<int,int>
#define pb push_back
#define xx first
#define yy second
#define MAXN 3005

using namespace std;


int N, K;

int seg[4 * maxn];
int idx[4 * maxn];
int lejzi[4 * maxn];
int niz[maxn];

void propagate(int node, int l, int r){
    if(lejzi[node]){
        if(l != r){
            lejzi[node * 2] += lejzi[node];
            lejzi[node * 2 + 1] += lejzi[node];
        }
        seg[node] += lejzi[node];
        lejzi[node] = 0;
    }
}

void init(int node, int l, int r){
    if(l == r){
        seg[node] = niz[l];
        idx[node] = l;
        return;
    }
    int mid = (l + r) / 2;
    init(node * 2, l, mid);
    init(node * 2 + 1, mid + 1, r);
    seg[node] = max(seg[node * 2], seg[node * 2 + 1]);
    if(seg[node * 2] < seg[node * 2 + 1])idx[node] = idx[node * 2];
    else idx[node] = idx[node * 2 + 1];
}

void apdejt(int node, int l, int r, int levo, int desno, int val){
    propagate(node, l, r);
    if(r < levo || l > desno)return;
    if(l >= levo && r <= desno){
        lejzi[node] += val;
        propagate(node, l, r);
        return;
    }
    int mid = (l + r) / 2;
    apdejt(node * 2, l, mid, levo, desno, val);
    apdejt(node * 2 + 1, mid + 1, r, levo, desno, val);
    seg[node] = max(seg[node * 2], seg[node * 2 + 1]);
    if(seg[node * 2] < seg[node * 2 + 1])idx[node] = idx[node * 2];
    else idx[node] = idx[node * 2 + 1];
}

pii query(int node, int l, int r, int levo, int desno){
    if(l >= levo && r <= desno)return {seg[node], idx[node]};
    if(r < levo || l > desno)return {-1e9, 1};
    int mid = (l + r) / 2;
    return max(query(node * 2, l, mid, levo, desno), query(node * 2 + 1, mid + 1, r, levo, desno));
}

int bit[maxn];


void apdejtbit(int x){
    while(x <= N){
        bit[x]++;
        x += (x&-x);
    }
}

int kveribit(int x){
    int res = 0;
    while(x > 0){
        res += bit[x];
        x -= (x&-x);
    }
    return res;
}


void namesti(int le, int ri){
    while(1){
        pii sta = query(1,1,N,le,ri);
        if(sta.xx < 0)break;
        apdejtbit(sta.yy);
        apdejt(1,1,N,sta.yy,sta.yy,-1e9-sta.xx);
    }
}

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

void podlej(int a, int b)
{
    a++;
    b++;
    apdejt(1,1,b,a,b,1);
    namesti(a,b);
}

int dojrzale(int a, int b)
{
    a++;
    b++;
    return kveribit(a) - kveribit(b - 1);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4061 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4017 ms 416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4070 ms 1152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4074 ms 1792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4069 ms 3072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4073 ms 3456 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4081 ms 3448 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4078 ms 6264 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4059 ms 11132 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4035 ms 11128 KB Time limit exceeded
2 Halted 0 ms 0 KB -