이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 ----------
int X[1500000],Y[1500000],A[1500000];
vpii updates,queries;
pii ans[1500000];
class comp1 {
public:
bool operator()(int a,int b) {
if (ans[a].first == ans[b].first) return a < b;
else return ans[a].first < ans[b].first;
}
};
class comp2 {
public:
bool operator()(int a,int b) {
if (ans[a].second == ans[b].second) return a < b;
else return ans[a].second < ans[b].second;
}
};
set<int,comp1> S1[1500000];
set<int,comp2> S2[1500000];
map<int,int> MM;
int findAns(int l,int r,vi q,int N) {
if (q.empty()) return 0;
int i;
vi c;
for (i = 0; i < q.size(); i++) {
int s = A[queries[q[i]].first],e = queries[q[i]].second;
if ((e < l) || (s > r)) continue;
if ((l >= s) && (r <= e)) S1[0].insert(q[i]),S2[0].insert(q[i]);
else c.pb(q[i]);
}
if (!S1[0].empty()) {
MM[0] = 0,MM[N] = -1;
int x = 1;
for (i = l; i <= r; i++) {
if (MM.count(updates[i].second)) continue;
int u = (--MM.lower_bound(updates[i].second))->second;
MM[updates[i].second] = x++;
if (updates[i].first == 1) {
auto it = S2[u].begin(),it2 = S2[u].end();
int f = -1;
while (1) {
if ((it != S2[u].end()) && (ans[*it].second < N-updates[i].second)) it++;
else {
f = 0;
break;
}
if ((it2 == S2[u].begin()) || (ans[*(--it2)].second < N-updates[i].second)) {
f = 1;
break;
}
}
if (f) {
swap(S1[u],S1[x-1]),swap(S2[u],S2[x-1]);
it2 = S2[x-1].end();
while ((it2 != S2[x-1].begin()) && (ans[*(--it2)].second >= N-updates[i].second)) {
S1[u].insert(*it2),S2[u].insert(*it2);
S1[x-1].erase(*it2),it2 = S2[x-1].erase(it2);
}
}
else {
it = S2[u].begin();
while ((it != S2[u].end()) && (ans[*it].second < N-updates[i].second)) {
S1[x-1].insert(*it),S2[x-1].insert(*it);
S1[u].erase(*it),it = S2[u].erase(it);
}
}
}
else {
auto it = S1[u].begin(),it2 = S1[u].end();
int f = -1;
while (1) {
if ((it != S1[u].end()) && (ans[*it].first < updates[i].second)) it++;
else {
f = 0;
break;
}
if ((it2 == S1[u].begin()) || (ans[*(--it2)].first < updates[i].second)) {
f = 1;
break;
}
}
if (f) {
it2 = S1[u].end();
while ((it2 != S1[u].begin()) && (ans[*(--it2)].first >= updates[i].second)) {
S1[x-1].insert(*it2),S2[x-1].insert(*it2);
S2[u].erase(*it2),it2 = S1[u].erase(it2);
}
}
else {
swap(S1[u],S1[x-1]),swap(S2[u],S2[x-1]);
it = S1[x-1].begin();
while ((it != S1[x-1].end()) && (ans[*it].first < updates[i].second)) {
S1[u].insert(*it),S2[u].insert(*it);
S2[x-1].erase(*it),it = S1[x-1].erase(it);
}
}
}
}
for (auto it = MM.begin(); it->second != -1; it++) {
auto it2 = it;
it2++;
int x1 = it->first,x2 = it2->first;
for (auto it3 = S1[it->second].begin(); it3 != S1[it->second].end(); it3++) {
ans[*it3].first = max(ans[*it3].first,x1);
ans[*it3].second = max(ans[*it3].second,N-x2);
}
S1[it->second].clear(),S2[it->second].clear();
}
MM.clear();
}
if (l != r) {
int m = (l+r) / 2;
findAns(l,m,c,N),findAns(m+1,r,c,N);
}
return 0;
}
int main() {
int i;
int N,M,Q;
int T,P,L;
scanf("%d %d %d",&N,&M,&Q);
for (i = 0; i < M; i++) scanf("%d %d",&X[i],&Y[i]),A[i] = 0;
for (i = 0; i < Q; i++) {
scanf("%d",&T);
if (T == 1) {
scanf("%d",&P),P--;
queries.pb(mp(P,(int) updates.size()-1));
}
else if (T == 2) {
scanf("%d",&L);
updates.pb(mp(1,N-L));
}
else if (T == 3) {
scanf("%d",&L);
updates.pb(mp(2,L+1));
}
else {
scanf("%d %d",&X[M],&Y[M]);
A[M++] = updates.size();
}
}
vi q;
for (i = 0; i < queries.size(); i++) ans[i] = mp(X[queries[i].first],Y[queries[i].first]),q.pb(i);
findAns(0,(int) updates.size()-1,q,N+1);
for (i = 0; i < queries.size(); i++) printf("%d %d\n",ans[i].first,ans[i].second);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
sweeping.cpp: In function 'int findAns(int, int, vi, int)':
sweeping.cpp:82:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < q.size(); i++) {
~~^~~~~~~~~~
sweeping.cpp: In function 'int main()':
sweeping.cpp:200:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < queries.size(); i++) ans[i] = mp(X[queries[i].first],Y[queries[i].first]),q.pb(i);
~~^~~~~~~~~~~~~~~~
sweeping.cpp:202:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < queries.size(); i++) printf("%d %d\n",ans[i].first,ans[i].second);
~~^~~~~~~~~~~~~~~~
sweeping.cpp:178: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:179:55: 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]),A[i] = 0;
~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
sweeping.cpp:181:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&T);
~~~~~^~~~~~~~~
sweeping.cpp:183:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&P),P--;
~~~~~~~~~~~~~~^~~~
sweeping.cpp:187:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&L);
~~~~~^~~~~~~~~
sweeping.cpp:191:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&L);
~~~~~^~~~~~~~~
sweeping.cpp:195:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&X[M],&Y[M]);
~~~~~^~~~~~~~~~~~~~~~~~~~~
# | 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... |