/*
TASK:
LANG: C++11
*/
#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#include <ctime>
#include <climits>
#include <cstdlib>
#include <cassert>
#include <deque>
#include <tuple>
#include <functional>
#include <iomanip>
using namespace std;
//#define GEN
#define LOCAL
const double Pi = acos(-1.0);
typedef long long ll;
typedef pair<int, int> pii;
typedef pair <ll, ll> pll;
#define Set(a, s) memset(a, s, sizeof (a))
#define Rd(r) ifstream cin(r)
#define Wt(w) ofstream cout(w)
#define SIO(f) Rd(((string)f+".in").c_str());Wt(((string)f+".out").c_str())
#define FASTIO ios::sync_with_stdio(0);cin.tie(0)
const int inf = 1000000007;
const ll llinf = 800000000000000119;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
//const int dx[8] = { 1, 1, 1, 0, 0, -1, -1, -1}, dy[8] = { 1, 0, -1, 1, -1, 1, 0, -1};
//to_string
string to_string(string s) {
#ifdef LOCAL
return '"' + s + '"';
#endif // LOCAL
return s;
}
string to_string(const char* s) {
return to_string((string)s);
}
string to_string(bool b) {
#ifdef LOCAL
return (b ? "true" : "false");
#endif // LOCAL
return to_string((int)b);
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto& x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
#define N 4
template <typename T>
string to_string(T* v) {
bool first = true;
string res = "{";
for (int i = 0; i < N; i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(*v);
v++;
}
res += "}";
return res;
}
//dprintf
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef LOCAL
#define dprintf(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define dprintf(...) 41
#endif
//vector output
template <class T>
ostream& operator<<(ostream& stream, vector <T> v) {
for (T i : v) {
stream << i << " ";
}
#ifdef LOCAL
stream << "\b";
#endif
return stream;
}
// cross product
int cross(int a1, int b1, int a2, int b2) { return (a1 * b2 - a2 * b1); }
int ccw(pii a, pii b, pii c) { return cross(b.first - a.first, b.second - a.second, c.first - a.first, c.second - a.second); }
//hi
void hi() { printf("hi\n"); }
void hi(string flag) { dprintf("hi (%s)\n", flag.c_str()); }
#ifndef SEGTREE_I_INCLUDED
#define SEGTREE_I_INCLUDED
struct segtree_node {
segtree_node* left_child, * right_child;
int left_bound, right_bound;
int sum;
int lazy;
void update_node(int val) {
sum = (right_bound - left_bound + 1) * val;
lazy = val;
// cout << "update_node " << left_bound << " " << right_bound << " " << sum << " " << lazy << endl;
}
void merge() {
sum = 0;
if (left_child != NULL) {
sum += left_child->sum;
}
if (right_child != NULL) {
sum += right_child->sum;
}
}
void prop() {
if (lazy == -1) return;
int mid = left_bound + (right_bound - left_bound) / 2;
if (left_child == NULL) left_child = new segtree_node(left_bound, mid);
left_child->update_node(lazy);
if (right_child == NULL) right_child = new segtree_node(mid + 1, right_bound);
right_child->update_node(lazy);
lazy = -1;
}
void update(int left, int right, int val) {
// cout << "update " << left_bound << " " << right_bound << " " << left << " " << right << " " << val << endl;
if (left_bound >= left && right_bound <= right) {
update_node(val);
return;
}
prop();
int mid = left_bound + (right_bound - left_bound) / 2;
if (left <= mid) {
if (left_child == NULL) {
left_child = new segtree_node(left_bound, mid);
}
left_child->update(left, right, val);
}
if (right > mid) {
if (right_child == NULL) {
right_child = new segtree_node(mid + 1, right_bound);
}
right_child->update(left, right, val);
}
merge();
}
int query(int left, int right) {
if (left_bound >= left && right_bound <= right) {
return sum;
}
prop();
int mid = left_bound + (right_bound - left_bound) / 2;
int res = 0;
if (left <= mid) {
if (left_child == NULL) {
left_child = new segtree_node(left_bound, mid);
}
res += left_child->query(left, right);
}
if (right > mid) {
if (right_child == NULL) {
right_child = new segtree_node(mid + 1, right_bound);
}
res += right_child->query(left, right);
}
return res;
}
segtree_node() {
left_child = right_child = NULL;
left_bound = right_bound = -1;
sum = 0; lazy = -1;
}
segtree_node(int left, int right) {
left_child = right_child = NULL;
left_bound = left; right_bound = right;
sum = 0; lazy = -1;
}
};
#endif
int main() {
segtree_node* segtree = new segtree_node(0, inf);
int c = 0;
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int d, x, y;
cin >> d >> x >> y;
if (d == 1) {
c = segtree->query(x + c, y + c);
cout << c << endl;
} else {
// cout << "updating " << endl;
segtree->update(x + c, y + c, 1);
}
// cout << c << endl;
// for (int a = 0; a <= 10; a++) {
// cout << segtree->query(a, a) << " ";
// }
// cout << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
29 ms |
4972 KB |
Output is correct |
| 5 |
Correct |
41 ms |
5996 KB |
Output is correct |
| 6 |
Correct |
46 ms |
5868 KB |
Output is correct |
| 7 |
Correct |
40 ms |
5996 KB |
Output is correct |
| 8 |
Correct |
237 ms |
44652 KB |
Output is correct |
| 9 |
Correct |
482 ms |
77548 KB |
Output is correct |
| 10 |
Correct |
500 ms |
85484 KB |
Output is correct |
| 11 |
Correct |
499 ms |
91884 KB |
Output is correct |
| 12 |
Correct |
514 ms |
94700 KB |
Output is correct |
| 13 |
Correct |
482 ms |
110444 KB |
Output is correct |
| 14 |
Correct |
487 ms |
111212 KB |
Output is correct |
| 15 |
Correct |
663 ms |
201836 KB |
Output is correct |
| 16 |
Correct |
679 ms |
203500 KB |
Output is correct |
| 17 |
Correct |
490 ms |
114924 KB |
Output is correct |
| 18 |
Correct |
484 ms |
114924 KB |
Output is correct |
| 19 |
Correct |
761 ms |
207860 KB |
Output is correct |
| 20 |
Correct |
672 ms |
207852 KB |
Output is correct |
