This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)
#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)
#define M 1000000007 // 998244353
using T=pair<int, int>;
ll n;
// only works if op == 2 only (second subtask)
T merge(T a, T b) {
if (max(a.K,b.K) + max(a.V,b.V) <= n) return pair(max(a.K, b.K), max(a.V, b.V));
return a;
}
T id = T(-1, -1);
struct SparseTable {
int n,log2=0;
vector<vector<T>> a = {{}};
SparseTable(const vector<T>& v) {
n = v.size();
while((1<<log2) <= n) {
++log2;
}
a.resize(log2);
a[0] = v;
for(int i=1,len=1;i<log2;++i,len*=2) {
a[i].resize(n + 1 - (1<<i));
for(int j=0;j<a[i].size();++j) {
a[i][j] = merge(a[i-1][j], a[i-1][j + len]);
}
}
}
SparseTable(){}
T query(int l, int r) { // [l,r)
if (l >= r) return id;
int len = __lg(r-l);
return merge(a[len][l], a[len][r- (1<<len)]);
}
} seg;
int main(){
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
ios_base::sync_with_stdio(false); cin.tie(0);
cout << fixed << setprecision(20);
cin >> n; G(m) G(q)
vector<pair<pl, ll>> dusts;
vector<T> ev(1, id);
F(i, 0, m) {
G(x) G(y)
dusts.emplace_back(pair(x, y), 0);
}
vector<pl> requests;
F(i, 0, q) {
G(t) if (t==1) {
G(p) --p;
ev.emplace_back(id);
requests.emplace_back(p, ev.size());
} else if (t == 2) {
G(l)
ev.emplace_back(n-l, -1);
} else if (t == 3) {
G(l)
ev.emplace_back(-1, n-l);
} else {
G(a) G(b)
dusts.emplace_back(pair(a, b), ev.size());
ev.emplace_back(id);
}
}
if (m <= 2000 and q <= 5000) {
SparseTable sparse(ev);
for (auto [didx, ed]: requests) {
auto [coords, st] = dusts[didx];
ll l = st, r = ed;
F(j, st, ed) coords = merge(coords, ev[j]);
auto [x, y] = coords;
cout << x << " " << y << '\n';
}
} else {
SparseTable sparse(ev);
for (auto [didx, ed]: requests) {
auto [coords, st] = dusts[didx];
ll l = st, r = ed;
auto [x, y] = merge(coords, seg.query(l, r));
cout << x << " " << y << '\n';
}
}
}
Compilation message (stderr)
sweeping.cpp: In constructor 'SparseTable::SparseTable(const std::vector<std::pair<int, int> >&)':
sweeping.cpp:49:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int j=0;j<a[i].size();++j) {
| ~^~~~~~~~~~~~
sweeping.cpp: In function 'int main()':
sweeping.cpp:99:16: warning: unused variable 'l' [-Wunused-variable]
99 | ll l = st, r = ed;
| ^
sweeping.cpp:99:24: warning: unused variable 'r' [-Wunused-variable]
99 | ll l = st, r = ed;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |