#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>;
T merge(T a, T b) {
return {max(a.K,b.K),max(a.V,b.V)};
}
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);
G(n) G(m) G(q)
if (m > 3000 || q > 6000) EX(-1)
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), dusts.size());
ev.emplace_back(id);
}
}
// SparseTable sparse(ev);
for (auto [didx, ed]: requests) {
auto [coords, st] = dusts[didx];
ll l = st, r = ed;
auto [x, y] = coords;
F(j, st, ed) {
auto [a, b] = ev[j];
if (max(x, a) + max(b, y) <= n) x = max(x, a), y = max(b, y);
}
cout << x << " " << y << '\n';
}
}
Compilation message
sweeping.cpp: In constructor 'SparseTable::SparseTable(const std::vector<std::pair<int, int> >&)':
sweeping.cpp:44: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]
44 | for(int j=0;j<a[i].size();++j) {
| ~^~~~~~~~~~~~
sweeping.cpp: In function 'int main()':
sweeping.cpp:95:12: warning: unused variable 'l' [-Wunused-variable]
95 | ll l = st, r = ed;
| ^
sweeping.cpp:95:20: warning: unused variable 'r' [-Wunused-variable]
95 | ll l = st, r = ed;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
