#define DEBUG 0
#include <bits/stdc++.h>
using namespace std;
#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}
// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
public:
template<typename T>
_Debug& operator,(T val) {
cout << val << endl;
return *this;
}
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif
// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back
// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;
// ---------- END OF TEMPLATE ----------
template<typename T1,typename T2>
ostream& operator<<(ostream& output,const pair<T1,T2> &p) {
output << "(" << p.first << "," << p.second << ")";
return output;
}
template<typename T>
ostream& operator<<(ostream& output,const vector<T> &v) {
unsigned int i;
bool f = 1;
for (i = 0; i < v.size(); i++) {
if (!f) output << " ";
output << v[i];
f = 0;
}
return output;
}
template<typename T>
ostream& operator<<(ostream& output,const list<T> &l) {
typename list<T>::const_iterator it;
bool f = 1;
for (it = l.begin(); it != l.end(); it++) {
if (!f) output << " ";
output << *it;
f = 0;
}
return output;
}
template<typename T1,typename T2>
ostream& operator<<(ostream& output,const map<T1,T2> &m) {
typename map<T1,T2>::const_iterator it;
bool f = 1;
for (it = m.begin(); it != m.end(); it++) {
if (!f) output << " ";
output << "(" << it->first << " -> " << it->second << ")";
f = 0;
}
return output;
}
template<typename T>
ostream& operator<<(ostream& output,const set<T> &s) {
typename set<T>::const_iterator it;
bool f = 1;
for (it = s.begin(); it != s.end(); it++) {
if (!f) output << " ";
output << *it;
f = 0;
}
return output;
}
int X[500000],Y[500000];
map<int,pii> MM;
struct func { int l,r,d,u,x,y; };
vector<func> f;
int insert(map<pii,pii> &M,int l,int r,pii p) {
//debug "here",l,r,p;
//debug M;
auto it = M.upper_bound(mp(l,2e9));
if (it != M.begin()) {
it--;
pair<pii,pii> q = *it;
if ((q.first.first <= l) && (l <= q.first.second)) {
M.erase(it);
if (l-1 >= q.first.first) M[mp(q.first.first,l-1)] = q.second;
M[mp(l,q.first.second)] = q.second;
}
}
//debug M;
it = M.upper_bound(mp(r,2e9));
if (it != M.begin()) {
it--;
pair<pii,pii> q = *it;
if ((q.first.first <= r) && (r <= q.first.second)) {
M.erase(it);
if (r+1 <= q.first.second) M[mp(r+1,q.first.second)] = q.second;
M[mp(q.first.first,r)] = q.second;
}
}
//debug M;
it = M.lower_bound(mp(l,0));
while ((it != M.end()) && (it->first.second <= r)) assert(it->first.second >= l),it = M.erase(it);
M[mp(l,r)] = p;
//debug M;
return 0;
}
struct node {
node *l,*r;
map<pii,pii> M;
int update(int s,int e,int as,int ae,int d,int u,pii p) {
//cout<<as<<","<<ae<<","<<d<<","<<u<<": "<<p.first<<","<<p.second<<endl;
//cout<<s<<","<<e<<endl;
if ((s >= as) && (e <= ae)) {
insert(M,d,u,p);
return 0;
}
int mid = (s+e) / 2;
if (as <= mid) {
if (l == NULL) l = new node(),l->l = l->r = NULL;
l->update(s,mid,as,ae,d,u,p);
}
if (ae >= mid+1) {
if (r == NULL) r = new node(),r->l = r->r = NULL;
r->update(mid+1,e,as,ae,d,u,p);
}
return 0;
}
pii query(int s,int e,int q,int qy) {
int mid = (s+e) / 2;
pii ans = mp(-1,-1);
auto it = M.upper_bound(mp(qy,2e9));
if (it != M.begin()) {
it--;
if ((it->first.first <= qy) && (qy <= it->first.second)) ans = it->second;
}
if (q <= mid) {
if (l != NULL) {
pii ans2 = l->query(s,mid,q,qy);
if (ans.first+ans.second < ans2.first+ans2.second) ans = ans2;
}
}
else {
if (r != NULL) {
pii ans2 = r->query(mid+1,e,q,qy);
if (ans.first+ans.second < ans2.first+ans2.second) ans = ans2;
}
}
return ans;
}
};
node *root;
int update(int x,int t,int N) {
auto it = MM.lower_bound(x);
if (it->first == x) return 0;
auto it2 = it;
it2--;
if (t == 1) {
f.pb((func){it2->first-it2->second.first,x-1,N-it->first,N-x-1,x,-1});
f.pb((func){it2->first-it2->second.first,x-1,N-it->first-it->second.second,N-it->first,x,N-it->first});
MM[x] = mp(it2->second.first+x-it2->first,0);
}
else {
f.pb((func){it2->first,x-1,N-it->first-it->second.second,N-x-1,-1,N-x});
f.pb((func){it2->first-it2->second.first,it2->first,N-it->first-it->second.second,N-x-1,it2->first,N-x});
MM[x] = mp(0,it->second.second+it->first-x);
}
func a = f[f.size()-2],b = f.back();
swap(a,b);
assert((a.l >= 0) && (a.d >= 0) && (a.r <= N+5) && (a.u <= N+5));
if ((a.l <= a.r) && (a.d <= a.u)) root->update(0,N+5,a.l,a.r,a.d,a.u,mp(a.x,a.y));
swap(a,b);assert((a.l >= 0) && (a.d >= 0) && (a.r <= N+5) && (a.u <= N+5));
if ((a.l <= a.r) && (a.d <= a.u)) root->update(0,N+5,a.l,a.r,a.d,a.u,mp(a.x,a.y));
return 0;
}
int main() {
int i;
int N,M,Q;
int T,P,L,A,B;
scanf("%d %d %d",&N,&M,&Q);
for (i = 0; i < M; i++) scanf("%d %d",&X[i],&Y[i]);
MM[0] = MM[N+1] = mp(0,0);
root = new node;
root->l = root->r = NULL;
for (i = 0; i < Q; i++) {
scanf("%d",&T);
if (T == 1) {
scanf("%d",&P),P--;
pii ans = root->query(0,N+6,X[P],Y[P]);
int xx = X[P],yy = Y[P];
if (ans.first != -1) xx = ans.first;
if (ans.second != -1) yy = ans.second;
printf("%d %d\n",xx,yy);/*
pii p = mp(xx,yy);
int j;
for (j = f.size()-1; j >= 0; j--) {
if ((X[P] >= f[j].l) && (X[P] <= f[j].r) && (Y[P] >= f[j].d) && (Y[P] <= f[j].u)) {
int xx = X[P],yy = Y[P];
if (f[j].x != -1) xx = f[j].x;
if (f[j].y != -1) yy = f[j].y;
printf("o:%d %d\n",xx,yy);
assert(p == mp(xx,yy));
break;
}
}
if (j < 0) printf("o:%d %d\n",X[P],Y[P]),assert(p == mp(X[P],Y[P]));*/
}
else if (T == 2) {
scanf("%d",&L);
update(N-L,1,N+1);
}
else if (T == 3) {
scanf("%d",&L);
update(L+1,2,N+1);
}
else {
scanf("%d %d",&A,&B);
assert(0);
}
}
return 0;
}
Compilation message
sweeping.cpp: In function 'int main()':
sweeping.cpp:221:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&N,&M,&Q);
~~~~~^~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:222:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i = 0; i < M; i++) scanf("%d %d",&X[i],&Y[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:227:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&T);
~~~~~^~~~~~~~~
sweeping.cpp:229:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&P),P--;
~~~~~~~~~~~~~~^~~~
sweeping.cpp:251:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&L);
~~~~~^~~~~~~~~
sweeping.cpp:255:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&L);
~~~~~^~~~~~~~~
sweeping.cpp:259:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&A,&B);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
194 ms |
18296 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13349 ms |
1386876 KB |
Output is correct |
| 2 |
Correct |
8004 ms |
1357792 KB |
Output is correct |
| 3 |
Correct |
8505 ms |
1435940 KB |
Output is correct |
| 4 |
Correct |
9256 ms |
1251372 KB |
Output is correct |
| 5 |
Correct |
5638 ms |
1136524 KB |
Output is correct |
| 6 |
Correct |
7942 ms |
1275436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13349 ms |
1386876 KB |
Output is correct |
| 2 |
Correct |
8004 ms |
1357792 KB |
Output is correct |
| 3 |
Correct |
8505 ms |
1435940 KB |
Output is correct |
| 4 |
Correct |
9256 ms |
1251372 KB |
Output is correct |
| 5 |
Correct |
5638 ms |
1136524 KB |
Output is correct |
| 6 |
Correct |
7942 ms |
1275436 KB |
Output is correct |
| 7 |
Correct |
8408 ms |
1353924 KB |
Output is correct |
| 8 |
Correct |
8690 ms |
1359456 KB |
Output is correct |
| 9 |
Correct |
8488 ms |
1355816 KB |
Output is correct |
| 10 |
Correct |
8739 ms |
1434640 KB |
Output is correct |
| 11 |
Correct |
9540 ms |
1251048 KB |
Output is correct |
| 12 |
Correct |
8005 ms |
1275552 KB |
Output is correct |
| 13 |
Correct |
7920 ms |
1249480 KB |
Output is correct |
| 14 |
Correct |
209 ms |
4216 KB |
Output is correct |
| 15 |
Correct |
664 ms |
29916 KB |
Output is correct |
| 16 |
Correct |
13576 ms |
1353284 KB |
Output is correct |
| 17 |
Correct |
7995 ms |
1276452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
