oj.uz

Submission #362462

# Submission time Handle Problem Language Result Execution time Memory
362462 2021-02-03T10:15:35 Z MasterTaster Watering can (POI13_kon) C++14
100 / 100
 805 ms 42476 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 || desno<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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 5 ms 620 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 2540 KB Output is correct
2 Correct 78 ms 3948 KB Output is correct
3 Correct 58 ms 3692 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 4168 KB Output is correct
2 Correct 141 ms 4076 KB Output is correct
3 Correct 130 ms 6508 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 7872 KB Output is correct
2 Correct 101 ms 10732 KB Output is correct
3 Correct 163 ms 7916 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 8812 KB Output is correct
2 Correct 162 ms 12908 KB Output is correct
3 Correct 402 ms 13900 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 9068 KB Output is correct
2 Correct 325 ms 20332 KB Output is correct
3 Correct 300 ms 14572 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 16492 KB Output is correct
2 Correct 587 ms 24044 KB Output is correct
3 Correct 726 ms 26604 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 29984 KB Output is correct
2 Correct 412 ms 40684 KB Output is correct
3 Correct 680 ms 38380 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 30132 KB Output is correct
2 Correct 427 ms 42476 KB Output is correct
3 Correct 805 ms 39276 KB Output is correct