1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| #include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define SZ(x) ((int)x.size())
#define all(x,size) x.begin()+1,x.begin()+size+1
#define all1(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(2e5)+10,MAXval=static_cast<ll>(1e18)+3;
ll N,T;
pll xy[MAXN];
struct cmpx{
bool operator()(pll a,pll b) const{
if(a.first!=b.first) return a.first<b.first;
return a.second<b.second;
}
};
struct cmpy{
bool operator()(pll a,pll b) const{
if(a.second!=b.second) return a.second<b.second;
return a.first<b.first;
}
};
set<pll,cmpx> stx;
set<pll,cmpy> sty;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll sx,sy;
cin>>N>>T>>sx>>sy;
FOR(i, 1, N){
cin>>xy[i].first>>xy[i].second;
stx.insert(xy[i]);
sty.insert(xy[i]);
}
FOR(i, 1, T){
char op;ll dis;
cin>>op>>dis;
if(op=='U'){
set<pll,cmpx>::iterator it=stx.lower_bound({sx,sy});
while(it!=stx.end() && it->first== sx && it->second<=sy+dis){
set<pll,cmpx>::iterator next_it=next(it);
sty.erase({it->first,it->second});
stx.erase(it);
it=next_it;
}
sy+=dis;
}else if(op=='D'){
set<pll,cmpx>::iterator it=stx.lower_bound({sx,sy});
if(it==stx.begin() || stx.empty()){
sy-=dis;
continue;
}
it--;
while(it!=stx.end() && it->first== sx && it->second>=sy-dis){
if(it==stx.begin()){
sty.erase({it->first,it->second});
stx.erase(it);
break;
}
set<pll,cmpx>::iterator prev_it=prev(it);
sty.erase({it->first,it->second});
stx.erase(it);
it=prev_it;
}
sy-=dis;
}else if(op=='R'){
set<pll,cmpy>::iterator it=sty.lower_bound({sx,sy});
while(it!=sty.end() && it->first<=sx+dis && it->second==sy){
set<pll,cmpy>::iterator next_it=next(it);
stx.erase({it->first,it->second});
sty.erase(it);
it=next_it;
}
sx+=dis;
}else {
set<pll,cmpy>::iterator it=sty.lower_bound({sx,sy});
if(it==sty.begin() || sty.empty()){
sx-=dis;
continue;
}
it--;
while(it!=sty.end() && it->first>=sx-dis && it->second==sy){
if(it==sty.begin()){
stx.erase({it->first,it->second});
sty.erase(it);
break;
}
set<pll,cmpy>::iterator prev_it=prev(it);
stx.erase({it->first,it->second});
sty.erase(it);
it=prev_it;
}
sx-=dis;
}
}
cout<<sx<<' '<<sy<<' '<<N-stx.size()<<'\n';
return 0;
}
|
