This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=5e5+7;
int pocz[3*LIM], czy[3*LIM], n, m, N=1;
pair<int,int>T[LIM], wynik[2*LIM];
vector<pair<int,int>>P;
vector<int>wierz[8*LIM];
void upd(int l, int r, int x) {
if(l>r) return;
l+=N; r+=N;
wierz[l].pb(x);
if(l!=r) wierz[r].pb(x);
while(l/2!=r/2) {
if(l%2==0) wierz[l+1].pb(x);
if(r%2==1) wierz[r-1].pb(x);
l/=2; r/=2;
}
}
void solve(int v, int l, int r) {
if(l<r) {
int mid=(l+r)/2;
solve(2*v, l, mid);
solve(2*v+1, mid+1, r);
}
for(auto i : wierz[v]) czy[i]=1;
while(l<=r) {
if(P[l].st==2) {
rep(i, m) if(czy[i] && T[i].nd<=P[l].nd) T[i].st=max(T[i].st, n-P[l].nd);
} else if(P[l].st==3) {
rep(i, m) if(czy[i] && T[i].st<=P[l].nd) T[i].nd=max(T[i].nd, n-P[l].nd);
} else if(czy[P[l].nd]) wynik[l]=T[P[l].nd];
++l;
}
for(auto i : wierz[v]) czy[i]=0;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int q;
cin >> n >> m >> q;
rep(i, m) cin >> T[i].st >> T[i].nd;
rep(i, q) {
int t;
cin >> t;
if(t==4) {
cin >> T[m].st >> T[m].nd;
pocz[m]=P.size();
++m;
} else {
int x;
cin >> x;
if(t==1) --x;
P.pb({t, x});
}
}
while(N<P.size()) N*=2;
while(P.size()<N) P.pb({2, 0});
rep(i, P.size()) wynik[i]={-1, -1};
rep(i, m) upd(pocz[i], P.size()-1, i);
solve(1, 0, N-1);
rep(i, P.size()) if(wynik[i].st!=-1) cout << wynik[i].st << " " << wynik[i].nd << '\n';
}
Compilation message (stderr)
sweeping.cpp: In function 'int main()':
sweeping.cpp:62:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | while(N<P.size()) N*=2;
| ~^~~~~~~~~
sweeping.cpp:63:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
63 | while(P.size()<N) P.pb({2, 0});
| ~~~~~~~~^~
sweeping.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
| ^
sweeping.cpp:64:3: note: in expansion of macro 'rep'
64 | rep(i, P.size()) wynik[i]={-1, -1};
| ^~~
sweeping.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
| ^
sweeping.cpp:67:3: note: in expansion of macro 'rep'
67 | rep(i, P.size()) if(wynik[i].st!=-1) cout << wynik[i].st << " " << wynik[i].nd << '\n';
| ^~~
# | 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... |