#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
typedef pair<int,int> pi;
struct pt{int x,y;}pos[200005];
int cmp1(pt a, pt b){return a.x<b.x;}
int cmp2(pt a, pt b){return a.y<b.y;}
struct x{int key, sub, type;};
bool operator<(x a, x b){return a.key == b.key ? (a.type < b.type) : (a.key > b.key);}
int a[200005],n;
int lim, tree[270000];
void initTree(){
for(lim = 1; lim <= n+1; lim <<= 1);
memset(tree,0,sizeof(tree));
}
void add(int x){
while (x <= lim) {
tree[x]++;
x += x & -x;
}
}
int sum(int x){
int res = 0;
while (x) {
res += tree[x];
x -= x & -x;
}
return res;
}
long long f(int s, int e){
long long res = 0;
if(e == s) return 0;
if(e - s < 1000){
for (int i=s; i<=e; i++) {
int lower=a[i];
int upper=1e9;
for (int j=i+1; j<=e; j++) {
if(upper>a[j] && a[j]>lower){
upper=a[j];
res++;
}
}
}
return res;
}
int m = (s+e)/2;
res = f(s,m) + f(m+1,e);
initTree();
set<pi> s_left, s_right;
set<pi> ::iterator it;
priority_queue<x> pq;
int lim;
for (int i=m; i>=s; i--) {
it = s_left.upper_bound(pi(a[i],0));
if(it == s_left.end()) lim = n+1;
else lim = (*it).first - 1;
s_left.insert(pi(a[i],lim));
pq.push({a[i],lim,0});
}
for (int i=m+1; i<=e; i++) {
it = s_right.upper_bound(pi(a[i],0));
if(it == s_right.begin()) lim = -1;
else{
it--;
lim = (*it).first;
}
pq.push({lim,a[i],1});
s_right.insert(pi(a[i],lim));
}
for (int i=s; i<=e; i++) {
x c = pq.top();
pq.pop();
if(c.type) add(c.sub);
else res += sum(c.sub) - sum(c.key - 1);
}
return res;
}
int main(){
scanf("%d",&n);
for (int i=0; i<n; i++) {
scanf("%d %d",&pos[i].x,&pos[i].y);
}
sort(pos,pos+n,cmp2);
for (int i=0; i<n; i++) {
pos[i].y = i+1;
}
sort(pos,pos+n,cmp1);
for (int i=0; i<n; i++) {
a[i] = pos[i].y;
}
long long r = f(0,n-1);
printf("%lld",r);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
4612 KB |
Output is correct |
2 |
Correct |
0 ms |
4612 KB |
Output is correct |
3 |
Correct |
0 ms |
4612 KB |
Output is correct |
4 |
Correct |
0 ms |
4612 KB |
Output is correct |
5 |
Correct |
0 ms |
4612 KB |
Output is correct |
6 |
Correct |
0 ms |
4612 KB |
Output is correct |
7 |
Correct |
0 ms |
4612 KB |
Output is correct |
8 |
Correct |
0 ms |
4612 KB |
Output is correct |
9 |
Correct |
0 ms |
4612 KB |
Output is correct |
10 |
Correct |
0 ms |
4612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
4944 KB |
Output is correct |
2 |
Correct |
20 ms |
4944 KB |
Output is correct |
3 |
Correct |
12 ms |
4944 KB |
Output is correct |
4 |
Correct |
8 ms |
4944 KB |
Output is correct |
5 |
Correct |
12 ms |
4944 KB |
Output is correct |
6 |
Correct |
12 ms |
4944 KB |
Output is correct |
7 |
Correct |
20 ms |
4944 KB |
Output is correct |
8 |
Correct |
12 ms |
4944 KB |
Output is correct |
9 |
Correct |
12 ms |
4944 KB |
Output is correct |
10 |
Correct |
16 ms |
4944 KB |
Output is correct |
11 |
Correct |
20 ms |
4944 KB |
Output is correct |
12 |
Correct |
8 ms |
4944 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1004 ms |
17020 KB |
Output is correct |
2 |
Correct |
1552 ms |
17056 KB |
Output is correct |
3 |
Correct |
1152 ms |
17020 KB |
Output is correct |
4 |
Correct |
912 ms |
17020 KB |
Output is correct |
5 |
Correct |
1192 ms |
17020 KB |
Output is correct |
6 |
Correct |
1380 ms |
17020 KB |
Output is correct |
7 |
Correct |
1464 ms |
17020 KB |
Output is correct |
8 |
Correct |
1516 ms |
17020 KB |
Output is correct |
9 |
Correct |
1020 ms |
17020 KB |
Output is correct |
10 |
Correct |
1072 ms |
17020 KB |
Output is correct |
11 |
Correct |
1320 ms |
17020 KB |
Output is correct |
12 |
Correct |
1468 ms |
17028 KB |
Output is correct |
13 |
Correct |
1524 ms |
17048 KB |
Output is correct |
14 |
Correct |
920 ms |
17020 KB |
Output is correct |
15 |
Correct |
1320 ms |
17020 KB |
Output is correct |
16 |
Correct |
1500 ms |
17028 KB |
Output is correct |
17 |
Correct |
784 ms |
12268 KB |
Output is correct |
18 |
Correct |
1448 ms |
17024 KB |
Output is correct |
19 |
Correct |
1448 ms |
17020 KB |
Output is correct |
20 |
Correct |
1440 ms |
17020 KB |
Output is correct |