oj.uz

답안 #298985

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
298985 2020-09-14T11:37:56 Z mat_v Watering can (POI13_kon) C++14
100 / 100
 637 ms 18808 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){
    //cout << node << " " << l << " " << r << "\n";
    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;
    }
    ff(i,1,n){
        if(niz[i] >= 0){
            niz[i] = -1e9;
            apdejtbit(i);
        }
    }
    init(1,1,n);
}

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

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

Compilation message

kon.cpp: In function 'void inicjuj(int, int, int*)':
kon.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
kon.cpp:105:5: note: in expansion of macro 'ff'
  105 |     ff(i,1,n){
      |     ^~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 0 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 2512 KB Output is correct
2 Correct 68 ms 2168 KB Output is correct
3 Correct 54 ms 2296 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 3384 KB Output is correct
2 Correct 126 ms 3320 KB Output is correct
3 Correct 108 ms 3320 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 5624 KB Output is correct
2 Correct 100 ms 5496 KB Output is correct
3 Correct 150 ms 3832 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 269 ms 6520 KB Output is correct
2 Correct 155 ms 6008 KB Output is correct
3 Correct 310 ms 5624 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 303 ms 6520 KB Output is correct
2 Correct 285 ms 9400 KB Output is correct
3 Correct 276 ms 6008 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 409 ms 11128 KB Output is correct
2 Correct 542 ms 10072 KB Output is correct
3 Correct 584 ms 10724 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 563 ms 18424 KB Output is correct
2 Correct 411 ms 18552 KB Output is correct
3 Correct 557 ms 16760 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 546 ms 18260 KB Output is correct
2 Correct 438 ms 18808 KB Output is correct
3 Correct 637 ms 16632 KB Output is correct