# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
7919 |
2014-08-25T08:28:57 Z |
gs14004 |
허수아비 (JOI14_scarecrows) |
C++ |
|
1660 ms |
18604 KB |
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
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;}
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 < 500){
for (int i=s; i<=e; i++) {
int lower=a[i];
int upper=1987654321;
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, s_right_old;
set<pi> ::iterator it,it2;
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));
}
for (int i=m+1; i<=e; i++) {
it = s_right_old.upper_bound(pi(a[i],0));
if(it == s_right_old.begin()) lim = -1;
else{
it--;
lim = (*it).first;
}
s_right_old.insert(pi(a[i],lim));
s_right.insert(pi(lim,a[i]));
}
s_left.insert(pi(1e6,1e6));
s_right.insert(pi(1e6,1e6));
it = s_left.begin();
it2 = s_right.begin();
for (int i=s; i<=e; i++) {
if((*it).first < (*it2).first){
res += sum((*it).second) - sum((*it).first - 1);
it++;
}
else{
add((*it2).second);
it2++;
}
}
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);
}
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
4876 KB |
Output is correct |
2 |
Correct |
16 ms |
4876 KB |
Output is correct |
3 |
Correct |
8 ms |
4876 KB |
Output is correct |
4 |
Correct |
8 ms |
4876 KB |
Output is correct |
5 |
Correct |
12 ms |
4876 KB |
Output is correct |
6 |
Correct |
16 ms |
4876 KB |
Output is correct |
7 |
Correct |
16 ms |
4876 KB |
Output is correct |
8 |
Correct |
12 ms |
4876 KB |
Output is correct |
9 |
Correct |
12 ms |
4876 KB |
Output is correct |
10 |
Correct |
16 ms |
4876 KB |
Output is correct |
11 |
Correct |
16 ms |
4876 KB |
Output is correct |
12 |
Correct |
12 ms |
4876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1056 ms |
18604 KB |
Output is correct |
2 |
Correct |
1644 ms |
18604 KB |
Output is correct |
3 |
Correct |
1096 ms |
18604 KB |
Output is correct |
4 |
Correct |
960 ms |
18604 KB |
Output is correct |
5 |
Correct |
1216 ms |
18604 KB |
Output is correct |
6 |
Correct |
1396 ms |
18604 KB |
Output is correct |
7 |
Correct |
1556 ms |
18604 KB |
Output is correct |
8 |
Correct |
1652 ms |
18604 KB |
Output is correct |
9 |
Correct |
1100 ms |
18604 KB |
Output is correct |
10 |
Correct |
1144 ms |
18604 KB |
Output is correct |
11 |
Correct |
1388 ms |
18604 KB |
Output is correct |
12 |
Correct |
1604 ms |
18604 KB |
Output is correct |
13 |
Correct |
1644 ms |
18604 KB |
Output is correct |
14 |
Correct |
956 ms |
18604 KB |
Output is correct |
15 |
Correct |
1412 ms |
18604 KB |
Output is correct |
16 |
Correct |
1660 ms |
18604 KB |
Output is correct |
17 |
Correct |
824 ms |
13720 KB |
Output is correct |
18 |
Correct |
1572 ms |
18604 KB |
Output is correct |
19 |
Correct |
1536 ms |
18604 KB |
Output is correct |
20 |
Correct |
1492 ms |
18604 KB |
Output is correct |