이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int b=2000, m= ((2e5+10)+b-1)/b, siz=2e5+10;
int q, t, ids, n, bc; int l[siz], r[siz]; bool unutra[siz];
vector< pair <int, int> > TRE; int mini[m], maxi[m];
vector<pair <int, int> > dulj[m]; vector<pair <int, int> > answer[m]; vector<pair <int, int> > tre;
int num(int val) {
return lower_bound(TRE.begin(), TRE.end(), make_pair (val, (int)-1e9))-TRE.begin();
}
int LESS(int rr, int k) {
if (bc<=0) return 0;
int ind=0, ans=0;
while (ind<bc && maxi[ind]<=rr) {
ans+=lower_bound(dulj[ind].begin(), dulj[ind].end(), make_pair(k, -1))-dulj[ind].begin(); ind+=1;
}
for (int i=0; i<dulj [ind].size(); i++) if (dulj [ind][i].second<=rr && dulj [ind][i].first<k) ans++;
return ans;
}
int MORE(int ll, int rr) {
if (bc<=0) return 0;
int ans=0, ind=bc-1;
while (ind>0 && mini[ind]>rr) {
ans+=(int)answer[ind].size()-(upper_bound(answer[ind].begin(), answer[ind].end(), make_pair(ll, (int)1e9))-answer[ind].begin()); ind-=1;
}
for (int i=0; i<answer[ind].size(); i++) if (answer[ind][i].first>ll && answer[ind][i].second>rr) ans++;
return ans;
}
int convert(int ll, int rr, int k) {
return LESS(rr, k)-LESS(ll-1, k);
}
int not_ok(int a1, int b1, int a2, int b2) {
return b1<a2 || b2<a1;
}
int query(int l1, int r1, int k) {
if (r1-l1+1<k) return 0;
int ans=n-(convert(l1+k-1, r1, k)+MORE(r1-k+1, r1)+num(l1+k-1));
for (int i=0; i<tre.size(); i++)
if (!k || (!not_ok(l[tre [i].first], r[tre [i].first], l1, r1) && min(r1, r[tre [i].first])-max(l1, l[tre [i].first])>=k-1)){
if (tre [i].second) ans--;
else ans++;
}
return ans;
}
void did() {
for (int i=0; i<tre.size(); i++) if (tre [i].second) unutra[tre [i].first]=1;
TRE.clear(); tre.clear();
for (int i=1; i<ids+1; i++) if (!unutra[i]) TRE.push_back({r[i], i});
sort(TRE.begin(), TRE.end()); n=TRE.size(); bc=(n+m-1)/m;
for (int b=0; b<=bc; b++) {
dulj[b].clear(); answer[b].clear();
}
for (int b=0; b<bc; b++) {
for (int i=b*m; i<min(n, (b+1)*m); i++){
int ind=TRE[i].second;
dulj[b].push_back({r[ind]-l[ind]+1, r[ind]});
answer[b].push_back({l[ind], r[ind]});
maxi[b]=r[ind]; if (i==b*m) mini[b]=r[ind];
}
sort(dulj[b].begin(), dulj[b].end()); sort(answer[b].begin(), answer[b].end());
}
return ;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> q >> t; int lA=0;
for (int i=1; i<=q; i++) {
if (!(i % b)) did();
int ty; cin >> ty;
if (ty==1) {
ids++; cin >> l[ids] >> r[ids]; l[ids]^=t*lA; r[ids]^=t*lA;
if (l[ids]>r[ids]) swap(l[ids], r[ids]);
tre.push_back({ids, 0});
}
else if (ty==2) {
int j; cin >> j; tre.push_back({j, 1});
}
else {
int l1, r1, k; cin >> l1 >> r1 >> k; l1^=t*lA; r1^=t*lA;
if (l1>r1) swap(l1, r1);
int ans=query(l1, r1, k); lA=ans;
cout << ans << '\n';
}
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
segments.cpp: In function 'int LESS(int, int)':
segments.cpp:16:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for (int i=0; i<dulj [ind].size(); i++) if (dulj [ind][i].second<=rr && dulj [ind][i].first<k) ans++;
| ~^~~~~~~~~~~~~~~~~~
segments.cpp: In function 'int MORE(int, int)':
segments.cpp:25:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for (int i=0; i<answer[ind].size(); i++) if (answer[ind][i].first>ll && answer[ind][i].second>rr) ans++;
| ~^~~~~~~~~~~~~~~~~~~
segments.cpp: In function 'int query(int, int, int)':
segments.cpp:37:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int i=0; i<tre.size(); i++)
| ~^~~~~~~~~~~
segments.cpp: In function 'void did()':
segments.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int i=0; i<tre.size(); i++) if (tre [i].second) unutra[tre [i].first]=1;
| ~^~~~~~~~~~~
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |