#include <bits/stdc++.h>
#include <fstream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define mod 1000000007
#define INF 1000000001
#define INF2 2000000000
///#define cin fin
///#define cout fout
using namespace std;
double const EPS = 1e-14;
const int P = 1007;
typedef long long ll;
///ofstream fout("herding.out");
///ifstream fin("herding.in");
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order, order_of_key
const int N = 1e5 + 5;
struct Node {
ll sum = 0, numl = 0, numr = 0;
bool lazy = false;
};
Node seg[N*64];
int cnt = 2;
void push(int x, ll l, ll r) {
if(l == r || seg[x].lazy == false) return;
ll mid = (l+r)/2;
if(seg[x].numl == 0) {
seg[x].numl = cnt; cnt++; }
if(seg[x].numr == 0) {
seg[x].numr = cnt; cnt++; }
seg[x].lazy = false;
int indxl = seg[x].numl, indxr = seg[x].numr;
seg[indxl].lazy = true;
seg[indxr].lazy = true;
seg[indxl].sum = (mid-l+1);
seg[indxr].sum = (r-(mid+1)+1);
}
void Update(int x, ll l, ll r, ll L, ll R) {
push(x,l,r);
if(l > R || r < L) {
return;
}
else if(l >= L && r <= R) {
seg[x].lazy = true;
seg[x].sum = (r-l+1);
}
else {
ll mid = (l+r)/2;
if(seg[x].numl == 0) {
seg[x].numl = cnt; cnt++;
}
if(seg[x].numr == 0) {
seg[x].numr = cnt; cnt++;
}
int indxl = seg[x].numl, indxr = seg[x].numr;
Update(indxl,l,mid,L,R); Update(indxr,mid+1,r,L,R);
seg[x].sum = seg[indxl].sum+seg[indxr].sum;
}
}
ll sol(int x, ll l, ll r, ll L, ll R) {
push(x,l,r);
if(l > R || r < L) {
return 0;
}
else if(l >= L && r <= R) {
return seg[x].sum;
}
else {
ll mid = (l+r)/2;
if(seg[x].numl == 0) {
seg[x].numl = cnt; cnt++;
}
if(seg[x].numr == 0) {
seg[x].numr = cnt; cnt++;
}
int indxl = seg[x].numl, indxr = seg[x].numr;
return sol(indxl,l,mid,L,R)+sol(indxr,mid+1,r,L,R);
}
}
int main()
{
ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
int m; cin >> m; ll c = 0;
while(m--) {
ll d, l, r; cin >> d >> l >> r;
if(d == 1) {
ll val = sol(1,1,INF,l+c,r+c);
cout << val << endl; c = val;
}
else {
Update(1,1,INF,l+c,r+c);
}
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
9 ms |
6748 KB |
Output is correct |
5 |
Correct |
11 ms |
8880 KB |
Output is correct |
6 |
Correct |
11 ms |
8872 KB |
Output is correct |
7 |
Correct |
11 ms |
8796 KB |
Output is correct |
8 |
Correct |
98 ms |
52052 KB |
Output is correct |
9 |
Correct |
200 ms |
89380 KB |
Output is correct |
10 |
Correct |
201 ms |
99544 KB |
Output is correct |
11 |
Correct |
189 ms |
107600 KB |
Output is correct |
12 |
Correct |
197 ms |
111660 KB |
Output is correct |
13 |
Correct |
176 ms |
137040 KB |
Output is correct |
14 |
Correct |
174 ms |
138280 KB |
Output is correct |
15 |
Runtime error |
1770 ms |
262144 KB |
Execution killed with signal 9 |
16 |
Halted |
0 ms |
0 KB |
- |