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;
#define LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()
#define int long long
//RSQ セグメント木
struct SegmentTree{
private:
int n;
vector<int> nodes;
const int DEFAULT = 0;
public:
void init(int N){ //初期化する O(N)
nodes.clear();
n = 1;
while(n < N) n *= 2;
n = 2 * n -1;
for(int i=0; i<n; i++) nodes.push_back(DEFAULT);
}
void update(int i, int x){ //値を変更する O(log N)
i += n / 2;
nodes[i] = x;
while(i > 0){
i = (i-1)/2; //親の取得は(i-1)/2
nodes[i] = nodes[i*2+1] + nodes[i*2+2]; //子の取得はi*2+1,i*2+2
}
}
int sum(int a, int b, int k=0, int l=0, int r=-1){ //[a,b)の最小値を求める O(log N)
if(r == -1) r = n/2+1;
if(r <= a || b <= l) return DEFAULT; //交差する場合
if(a <= l && r <= b) return nodes[k]; //完全に含む場合
int valueL = sum(a, b, k*2+1, l, (l+r)/2);
int valueR = sum(a, b, k*2+2, (l+r)/2, r);
return valueL + valueR;
}
};
int N;
pair<int,int> point[200000];
//数学と同じ座標の取り方→xとyの大小関係一致
vector<int> zaatuX,zaatuY;
LL ans = 0;
void DevideConquer(int l, int r){
if(r-l == 1) return;
int m = (l+r)/2;
vector<int> zaatu;
for(int i=l; i<r; i++) zaatu.PB(point[i].second);
sort(zaatu.begin(), zaatu.end());
set<int> st1,st2;
vector<pair<pair<int,int>,int>> kukan;
for(int i=m-1; i>=l; i--){
int y = lower_bound(zaatu.begin(), zaatu.end(), point[i].second) - zaatu.begin();
auto itr = st1.lower_bound(y);
if(itr == st1.end()) kukan.PB(MP(MP(y,N),0));
else kukan.PB(MP(MP(y,*itr),0));
st1.insert(y);
}
for(int i=m; i<r; i++){
int y = lower_bound(zaatu.begin(), zaatu.end(), point[i].second) - zaatu.begin();
auto itr = st2.lower_bound(y);
if(itr == st2.begin()) kukan.PB(MP(MP(0,y),1));
else{
itr--;
kukan.PB(MP(MP(*itr,y),1));
}
st2.insert(y);
}
sort(kukan.begin(), kukan.end());
SegmentTree rsq; //右サイドの上端
rsq.init(r-l);
for(int i=0; i<kukan.size(); i++){
if(kukan[i].second == 0){
ans += rsq.sum(kukan[i].first.first, kukan[i].first.second);
}
else{
rsq.update(kukan[i].first.second, 1);
}
}
DevideConquer(l, m);
DevideConquer(m, r);
}
signed main(){
scanf("%d", &N);
for(int i=0; i<N; i++){
scanf("%d%d", &point[i].first, &point[i].second);
zaatuX.PB(point[i].first);
zaatuY.PB(point[i].second);
}
sort(zaatuX.begin(), zaatuX.end());
sort(zaatuY.begin(), zaatuY.end());
for(int i=0; i<N; i++){
point[i].first = lower_bound(zaatuX.begin(), zaatuX.end(), point[i].first) - zaatuX.begin();
point[i].second = lower_bound(zaatuY.begin(), zaatuY.end(), point[i].second) - zaatuY.begin();
}
sort(point, point+N);
//
DevideConquer(0, N);
printf("%lld\n", ans);
return 0;
}
Compilation message (stderr)
scarecrows.cpp: In function 'void DevideConquer(long long int, long long int)':
scarecrows.cpp:81:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<kukan.size(); i++){
~^~~~~~~~~~~~~
scarecrows.cpp: In function 'int main()':
scarecrows.cpp:95:16: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
scanf("%d", &N);
~~^
scarecrows.cpp:97:50: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
scanf("%d%d", &point[i].first, &point[i].second);
~~~~~~~~~~~~~~~ ^
scarecrows.cpp:97:50: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
scarecrows.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
scarecrows.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &point[i].first, &point[i].second);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |