#include <bits/stdc++.h>
#include "koninc.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 + 50;
vector<int> sum(4*N), maks(4*N);
vector<int> a(N);
int d;
vector<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)
{
if(i>j) return;
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) return;
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>j) return 0;
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)
{
if(l>r) return;
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:95:37: warning: value computed is not used [-Wunused-value]
95 | 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:42:60: warning: control reaches end of non-void function [-Wreturn-type]
42 | 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:95:46: warning: control reaches end of non-void function [-Wreturn-type]
95 | get_sum(node*2+1, l, r, i, mid) + get_sum(node*2+2, l, r, mid+1, j);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
31340 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
31340 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
36 ms |
31596 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
36 ms |
31724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
44 ms |
32108 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
54 ms |
32364 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
51 ms |
32364 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
73 ms |
33132 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
79 ms |
33644 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
99 ms |
33772 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
