/* nya */
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma")
#include <bits/stdc++.h>
#define For(i, a, b) for (int i = a; i <= b; i++)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
#define INF (int)(1e18)
#define MOD (int)(1000000007)
// #define MOD (int)(998244353)
using namespace std;
using LL = long long;
// using LLL = __int128_t;
using pii = pair<int, int>;
#ifdef NYAOWO
#include "library/debug.hpp"
inline void USACO(const string &s) {
cerr << "USACO: " << s << "\n";
}
#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
#endif
struct Nyacho {
int typ, l, r, cost;
};
ostream& operator<<(ostream& os, const Nyacho nya) {
if(nya.typ) cout << nya.l << "->" << nya.r << " (" << nya.cost << ")";
else cout << nya.l << "::" << nya.r << " (" << nya.cost << ")";
return os;
}
#define dist(x, l, r) max(0ll, (x) - (r))
#define clamp(x, l, r) max(l, min(r, x))
Nyacho merge(const Nyacho &a, const Nyacho &b) {
Nyacho c;
if(a.typ == 0 && b.typ == 0) {
if(min(a.r, b.r) < max(a.l, b.l)) {
if(a.r < b.r) c = {1, a.r, b.l, 0};
else c = {1, a.l, b.r, a.l - b.r};
} else {
c = {0, max(a.l, b.l), min(a.r, b.r), 0};
}
} else if(a.typ == 0) {
c = {1, clamp(b.l, a.l, a.r), b.r, max(0ll, a.l - b.l)};
} else if(b.typ == 0) {
c = {1, a.l, clamp(a.r, b.l, b.r), max(0ll, a.r - b.r)};
} else {
c = {1, a.l, b.r, max(0ll, a.r - b.l)};
}
c.cost += a.cost + b.cost;
return c;
}
const int MAXN = 300030;
Nyacho nya[MAXN];
Nyacho ayn[MAXN];
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
// OAO
int n, q; cin >> n >> q;
assert(max(n, q) <= 1000);
For(i, 1, n - 1) {
int l, r; cin >> l >> r; r--;
nya[i] = {0, l - i, r - i, 0};
ayn[i] = {0, l + i, r + i, 0};
//cout << nya[i] << " " << ayn[i] << "\n";
}
while(q--) {
int op; cin >> op;
if(op == 1) {
int p, s, e; cin >> p >> s >> e; e--;
nya[p] = {0, s - p, e - p, 0};
} else {
int a, b, c, d; cin >> a >> b >> c >> d;
Nyacho res;
if(a < c) {
c--; b -= a; d -= c + 1;
res = {0, b, b, 0};
For(i, a, c) {
res = merge(res, nya[i]);
//cout << res << "\n";
}
} else {
a--; b += a; d += c - 1;
res = {0, b, b, 0};
Forr(i, a, c) {
res = merge(res, ayn[i]);
//cout << res << "\n";
}
}
res = merge(res, {0, d, d, 0});
cout << res.cost << "\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
