oj.uz

Submission #343417

# Submission time Handle Problem Language Result Execution time Memory
343417 2021-01-03T22:51:31 Z iliccmarko Watering can (POI13_kon) C++14
0 / 100
 55 ms 5356 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 1000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define single_case solve();
#define line cerr<<"----------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL); }
#define mod 1000000007LL
const int N = 3e5 + 5;
int sum[4*N], maks[4*N];
int a[N];
int d;
int lazy[4*N];
int n;

int buildsum(int node, int l, int r)
{
    if(l==r)
    {
        return sum[node] = (a[l]>=d)?1:0;
    }
    int mid = (l+r)/2;
    return sum[node] = buildsum(node*2+1, l, mid) + buildsum(node*2+2, mid+1, r);
}

int buildmaks(int node, int l, int r)
{
    if(l==r)
    {
        if(a[l]>=d) maks[node] = -N;
        else maks[node] = a[l];
        return maks[node];
    }
    int mid = (l+r)/2;
    maks[node] = max(buildmaks(node*2+1, l, mid), buildmaks(node*2+2, mid+1, r));
}

void updatemaks(int node, int l, int r, int i, int j)
{
    int mid = (i+j)/2;
    if(lazy[node])
    {
        if(i!=j)
        {
            lazy[node*2+1] += lazy[node];
            lazy[node*2+2] += lazy[node];
        }
        maks[node] += lazy[node];
        lazy[node] = 0;
    }
    if(i>r||j<l) return;
    if(i>=l&&j<=r)
    {
        maks[node]++;
        if(i!=j)
        {
            lazy[node*2+1]++;
            lazy[node*2+2]++;
        }
        return;
    }
    updatemaks(node*2+1, l, r, i, mid);
    updatemaks(node*2+2, l, r, mid+1, j);
    maks[node] = max(maks[node*2+1], maks[node*2+2]);
}

void updatesum(int node, int l, int r, int x)
{
    if(l==r)
    {
        sum[node] = 1;
        return;
    }
    int mid = (l+r)/2;
    if(x>mid) updatesum(node*2+2, mid+1, r, x);
    else updatesum(node*2+1, l, mid, x);
    sum[node] = sum[node*2+1] + sum[node*2+2];
}

int get_sum(int node, int l, int r, int i, int j)
{
    if(i>r||j<l) return 0;
    if(i>=l&&j<=r) return sum[node];
    int mid = (i+j)/2;
    get_sum(node*2+1, l, r, i, mid) + get_sum(node*2+2, l, r, mid+1, j);
}

void trazi(int node, int l, int r)
{
    int mid = (l+r)/2;
    if(lazy[node])
    {
        if(l!=r)
        {
            lazy[node*2+1] += lazy[node];
            lazy[node*2+2] += lazy[node];
        }
        maks[node] += lazy[node];
        lazy[node] = 0;
    }
    if(maks[node]<d) return;
    if(l==r)
    {
        updatesum(0, 0, n-1, l);
        maks[node] = -N;
        return;
    }
    //int mid = (l+r)/2;
    trazi(node*2+1, l, mid);
    trazi(node*2+2, mid+1, r);
    maks[node] = max(maks[node*2+1], maks[node*2+2]);
}

void inicjuj(int w, int k, int *D)
{
    for(int i = 0;i<w;i++) a[i] = D[i];
    d = k;
    n = w;
    buildmaks(0, 0, n-1);
    buildsum(0, 0, n-1);
}

void podlej(int a, int b)
{
    updatemaks(0, a, b, 0, n-1);
}

int dojrzale(int a, int b)
{
    trazi(0, 0, n-1);
    return get_sum(0, a, b, 0, n-1);
}

Compilation message

kon.cpp: In function 'int get_sum(int, int, int, int, int)':
kon.cpp:91:37: warning: value computed is not used [-Wunused-value]
   91 |     get_sum(node*2+1, l, r, i, mid) + get_sum(node*2+2, l, r, mid+1, j);
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
kon.cpp: In function 'int buildmaks(int, int, int)':
kon.cpp:41:60: warning: control reaches end of non-void function [-Wreturn-type]
   41 |     maks[node] = max(buildmaks(node*2+1, l, mid), buildmaks(node*2+2, mid+1, r));
      |                                                   ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
kon.cpp: In function 'int get_sum(int, int, int, int, int)':
kon.cpp:91:46: warning: control reaches end of non-void function [-Wreturn-type]
   91 |     get_sum(node*2+1, l, r, i, mid) + get_sum(node*2+2, l, r, mid+1, j);
      |                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 1260 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 1260 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 2668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 2668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 4076 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 5228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 5356 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -