oj.uz

Submission #362459

# Submission time Handle Problem Language Result Execution time Memory
362459 2021-02-03T10:11:23 Z MasterTaster Watering can (POI13_kon) C++14
0 / 100
 531 ms 41512 KB 
#include<bits/stdc++.h>

#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define MAXN 300010
#define INF 2000000010

using namespace std;

int N, K, a[MAXN];

int bit[MAXN];
pair<ll, int> seg[4*MAXN];
ll lazy[4*MAXN];

void upd(int x)
{
    while (x<MAXN)
    {
        bit[x]++;
        x+=x&(-x);
    }
}
int sum(int x)
{
    int ret=0;
    while (x)
    {
        ret+=bit[x];
        x-=x&(-x);
    }
    return ret;
}
void relax(int node, int l, int r)
{
    seg[node].xx+=lazy[node];
    if (l!=r)
    {
        lazy[2*node]+=lazy[node];
        lazy[2*node+1]+=lazy[node];
    }
    lazy[node]=0;
}
void build(int node, int l, int r)
{
    if (l==r) { seg[node]={a[l], l}; return; }
    int mid=l+(r-l)/2;
    build(2*node, l, mid);
    build(2*node+1, mid+1, r);
    seg[node]=max(seg[2*node], seg[2*node+1]);
}
void update(int node, int l, int r, int levo, int desno, int val) ///[l,r]-gde sam u segmentnom; [levo,desno]-query;
{
    relax(node, l, r);
    if (levo>r || levo<l) return;
    if (levo<=l && desno>=r) { lazy[node]+=val; return; }

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

    int mid=l+(r-l)/2;
    return max(query(2*node, l, mid, levo, desno),
               query(2*node+1, mid+1, r, levo, desno));
}

void inicjuj(int n, int k, int *D)
{
    N = n, K = k;
    for (int i = 0; i < n; ++i)
    {
        a[i+1] = D[i];
        if (a[i+1]>=k) { a[i+1]=-INF; upd(i+1); }
    }
    build(1, 1, n);
}

void podlej(int a, int b)
{
    a++; b++;
    update(1, 1, N, a, b, 1);

    pii maxx=query(1, 1, N, a, b);
    while (maxx.xx>=K)
    {
        upd(maxx.yy);
        update(1, 1, N, maxx.yy, maxx.yy, -INF);
        maxx=query(1, 1, N, a, b);
    }
}

int dojrzale(int a, int b)
{
    a++; b++;
    return sum(b)-sum(a-1);
    //return (t[a] >= K) + (t[b] >= K); /* cos glupiego */
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 4076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 6252 KB Output is correct
2 Incorrect 135 ms 6484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 10988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 278 ms 15028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 283 ms 15468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 422 ms 25308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 523 ms 41044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 531 ms 41512 KB Output isn't correct
2 Halted 0 ms 0 KB -