#include <iostream>
#include <string.h>
#include <random>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iomanip>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <valarray>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef pair<int, int> pii;
typedef pair<int, string> pis;
typedef pair<int, short> pish;
typedef pair<string, string> pss;
typedef pair<int, char> pic;
typedef pair<pii, int> piii;
typedef pair<double, double> pdd;
typedef pair<float, float> pff;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> plll;
typedef pair<pll, ld> plld;
typedef pair<int, ll> pil;
typedef pair<ull, ull> pull;
typedef pair<ld, ld> pld;
typedef complex<double> cd;
//#define max(n, m) ((n>m)?n:m)
//#define min(n, m) ((n<m)?n:m)
#define f first
#define s second
#define input() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define eps 1e-9
//#define cin fin
struct node
{
int l, r;
node* left = nullptr;
node* right = nullptr;
int val;
bool lazy;
node(int l, int r, node* left, node* right, int val)
{
this->l = l; this->r = r; this->left = left; this->right = right; this->val = val;
}
};
void update(node* cur, int lq, int rq)
{
int mid = (cur->l + cur->r) / 2;
if(cur->lazy && (cur->l == cur->r || (cur->left != nullptr || cur->right != nullptr)))
{
cur->val = (cur->r - cur->l + 1);
if(cur->l != cur->r)
{
if(cur->left == nullptr)
cur->left = new node(cur->l, mid, nullptr, nullptr, 0);
if(cur->right == nullptr)
cur->right = new node(mid+1, cur->r, nullptr, nullptr, 0);
cur->left->lazy = true;
cur->right->lazy = true;
}
cur->lazy = false;
}
if(cur->l > rq || cur->r < lq || cur->l > cur->r) return;
if(cur->l >= lq && cur->r <= rq)
{
cur->val = (cur->r - cur->l + 1);
if(cur->l != cur->r)
{
if(cur->left == nullptr)
cur->left = new node(cur->l, mid, nullptr, nullptr, 0);
if(cur->right == nullptr)
cur->right = new node(mid+1, cur->r, nullptr, nullptr, 0);
cur->left->lazy = true;
cur->right->lazy = true;
}
return;
}
if(cur->left == nullptr)
cur->left = new node(cur->l, mid, nullptr, nullptr, 0);
update(cur->left, lq, rq);
if(cur->right == nullptr)
cur->right = new node(mid+1, cur->r, nullptr, nullptr, 0);
update(cur->right, lq, rq);
int num = 0;
if(cur->left != nullptr) num += cur->left->val;
if(cur->right != nullptr) num += cur->right->val;
cur->val = num;
}
int sum(node* cur, int lq, int rq)
{
int mid = (cur->l + cur->r) / 2;
if(cur->lazy && (cur->l == cur->r || (cur->left != nullptr || cur->right != nullptr)))
{
cur->val = (cur->r - cur->l + 1);
if(cur->l != cur->r)
{
if(cur->left == nullptr)
cur->left = new node(cur->l, mid, nullptr, nullptr, 0);
if(cur->right == nullptr)
cur->right = new node(mid+1, cur->r, nullptr, nullptr, 0);
cur->left->lazy = true;
cur->right->lazy = true;
}
cur->lazy = false;
}
if(cur->l > rq || cur->r < lq || cur->l > cur->r) return 0;
if(cur->l >= lq && cur->r <= rq)
return cur->val;
int num = 0;
if(cur->left != nullptr) num += sum(cur->left, lq, rq);
if(cur->right != nullptr) num += sum(cur->right, lq, rq);
return num;
}
int main()
{
input();
int m, type, a, b;
int c = 0;
cin >> m;
node* root = new node(0, 1100000000, nullptr, nullptr, 0);
while(m--)
{
cin >> type >> a >> b; a--; b--; a+=c; b+=c;
if(type == 1)
{
c = sum(root, a, b);
cout << c << "\n";
}
else
update(root, a, b);
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
