#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define int long long
#define ft first
#define sc second
using namespace std;
const int mod=1e9+7,INF=1e17;
const int inf = 1e9;
struct node {
int sum;
int lz;
node *c[2];
node(int x=0,int l=-1) : sum(x), lz(l){
c[0] = c[1] = NULL;
}
};
node operator + (node a,node b){
node c(a.sum+b.sum);
return c;
}
const int N=1e6;
void push(node *p,int len){
if (p->lz == -1) return;
p->sum=len*p->lz;
if(p->c[0] != NULL){
p->c[0]->lz = p->c[1]->lz = p->lz;
}
// p->lz=-1;
}
void update(node *p,int l,int r,int x,int y,int v){
push(p,r-l+1);
if(x>r || y<l){
return;
}
if(x<=l && y>=r){
p->lz = v;
push(p,r-l+1);
return;
}
if (p->c[0] == NULL) p->c[0] = new node();
if (p->c[1] == NULL) p->c[1] = new node();
int m=(l+r)/2;
update(p->c[0],l,m,x,y,v);
update(p->c[1],m+1,r,x,y,v);
p->sum = p->c[0]->sum + p->c[1]->sum;
}
int query(node *p,int l,int r,int x,int y){
push(p,r-l+1);
if(x>r || y<l){
return 0;
}
if(x<=l && y>=r){
return p->sum;
}
if (p->c[0] == NULL) p->c[0] = new node();
if (p->c[1] == NULL) p->c[1] = new node();
int m=(r+l)/2;
return query(p->c[0],l,m,x,y) + query(p->c[1],m+1,r,x,y);
}
main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,q;
cin >> q;
int c=0;
node *root = new node();
while(q--){
int type;
cin >> type;
if(type==2){
int l,r,v;
cin >> l >> r;
update(root,1,inf,l+c,r+c,1);
}
else{
int l,r;
cin >> l >> r;
c=query(root,1,inf,l+c,r+c);
cout << c << "\n";
}
}
}
Compilation message
apple.cpp:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
63 | main(){
| ^~~~
apple.cpp: In function 'int main()':
apple.cpp:73:12: warning: unused variable 'v' [-Wunused-variable]
73 | int l,r,v;
| ^
apple.cpp:65:6: warning: unused variable 'n' [-Wunused-variable]
65 | int n,q;
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
