| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 393667 |
2021-04-24T08:18:56 Z |
79brue |
Fire (JOI20_ho_t5) |
C++14 |
|
999 ms |
48144 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Triangle{
int x, y; ll w;
Triangle(){}
Triangle(int x, int y, ll w): x(x), y(y), w(w){}
bool operator<(const Triangle &r)const{
return x<r.x;
}
};
struct Query{
int t, l, r, idx;
Query(){}
Query(int t, int l, int r, int idx): t(t), l(l), r(r), idx(idx){}
bool operator<(const Query &r)const{
return t < r.t;
}
};
struct maxSegmentTree{
ll tree[800002];
void init(int i, int l, int r, ll A[]){
if(l==r){
tree[i] = A[l];
return;
}
int m = (l+r)>>1;
init(i*2, l, m, A);
init(i*2+1, m+1, r, A);
tree[i] = max(tree[i*2], tree[i*2+1]);
}
int biggerLim(int i, int l, int r, int x, ll lim, int dir){ /// bigger than lim / dir=0: left, dir=1: right
if(tree[i] <= lim) return dir==0 ? l-1 : r+1;
if(l==r) return l;
int m = (l+r)>>1;
if(dir == 0){
if(x<=m) return biggerLim(i*2, l, m, x, lim, dir);
int tmp = biggerLim(i*2+1, m+1, r, x, lim, dir);
if(tmp > m) return tmp;
return biggerLim(i*2, l, m, x, lim, dir);
}
else{
if(m<x) return biggerLim(i*2+1, m+1, r, x, lim, dir);
int tmp = biggerLim(i*2, l, m, x, lim, dir);
if(tmp <= m) return tmp;
return biggerLim(i*2+1, m+1, r, x, lim, dir);
}
}
} maxSeg;
struct lazySegmentTree{
ll tree[1600002], lazy[1600002];
void init(int i, int l, int r){
tree[i] = lazy[i] = 0;
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m), init(i*2+1, m+1, r);
}
void propagate(int i, int l, int r){
tree[i] += lazy[i] * (r-l+1);
if(l!=r){
lazy[i*2] += lazy[i];
lazy[i*2+1] += lazy[i];
}
lazy[i] = 0;
}
void addRange(int i, int l, int r, int s, int e, ll val){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazy[i] += val;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
addRange(i*2, l, m, s, e, val);
addRange(i*2+1, m+1, r, s, e, val);
tree[i] = tree[i*2] + tree[i*2+1];
}
ll rangeSum(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return 0;
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return rangeSum(i*2, l, m, s, e) + rangeSum(i*2+1, m+1, r, s, e);
}
} segRight, segDiag;
int n, q;
ll arr[200002];
Query query[200002];
ll ans[200002];
vector<Triangle> triangle;
void input();
void makeTriangles();
void sweep();
int main(){
input();
makeTriangles();
sweep();
for(int i=1; i<=q; i++) printf("%lld\n", ans[i]);
}
void input(){
scanf("%d %d", &n, &q);
for(int i=1; i<=n; i++){
scanf("%lld", &arr[i]);
}
for(int i=1; i<=q; i++){
scanf("%d %d %d", &query[i].t, &query[i].l, &query[i].r);
query[i].idx = i;
query[i].t++;
}
}
void makeTriangles(){
maxSeg.init(1, 1, n, arr);
for(int i=1; i<=n; i++){
triangle.push_back(Triangle(1, i, arr[i]));
int rLim = maxSeg.biggerLim(1, 1, n, i+1, arr[i]-1, 1);
if(i<n && rLim <= n) triangle.push_back(Triangle(rLim - i + 1, rLim, -arr[i]));
int lLim = maxSeg.biggerLim(1, 1, n, i-1, arr[i], 0);
if(i>1 && lLim >= 1) triangle.push_back(Triangle(i - lLim + 1, i, -arr[i]));
if(i<n && i>1 && rLim <= n && lLim >= 1){
triangle.push_back(Triangle((rLim - i + 1) + (i - lLim + 1) - 1, rLim, arr[i]));
}
}
sort(triangle.begin(), triangle.end());
}
void sweep(){
segRight.init(1, 1, n);
segDiag.init(1, -n, n);
if(n > 200) q = min(q, 100000);
int pnt = 0, qpnt = 1;
for(int i=1; i<=n+1; i++){
while(pnt < (int)triangle.size() && triangle[pnt].x <= i){
Triangle tri = triangle[pnt++];
segRight.addRange(1, 1, n, 1, tri.y - 1, -tri.w);
segDiag.addRange(1, -n, n, -n, tri.y - tri.x, tri.w);
}
while(qpnt <= q && query[qpnt].t <= i){
Query qr = query[qpnt++];
ans[qr.idx] += segRight.rangeSum(1, 1, n, qr.l, qr.r);
ans[qr.idx] += segDiag.rangeSum(1, -n, n, qr.l - qr.t, qr.r - qr.t);
}
}
}
Compilation message
ho_t5.cpp: In function 'void input()':
ho_t5.cpp:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
118 | scanf("%d %d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~
ho_t5.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
120 | scanf("%lld", &arr[i]);
| ~~~~~^~~~~~~~~~~~~~~~~
ho_t5.cpp:123:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
123 | scanf("%d %d %d", &query[i].t, &query[i].l, &query[i].r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
999 ms |
48144 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
919 ms |
47780 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
789 ms |
44120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
