oj.uz

Submission #163214

# Submission time Handle Problem Language Result Execution time Memory
163214 2019-11-11T20:11:42 Z TadijaSebez 허수아비 (JOI14_scarecrows) C++11
100 / 100
 1875 ms 9452 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=200050;
const int S=447;
const int H=N/S+1;
int SEQ[H][S],a[N],ptr[H];
bool use[N+S];
void Build(int B)
{
	int l=B*S,r=(B+1)*S-1;
	ptr[B]=0;
	for(int i=r;i>=l;i--) if(use[i])
	{
		while(ptr[B] && SEQ[B][ptr[B]-1]>a[i]) ptr[B]--;
		SEQ[B][ptr[B]++]=a[i];
	}
}
void Add(int pos)
{
	use[pos]=1;
	int B=pos/S;
	Build(B);
}
int x[N],y[N],id[N],stk[N],top;
vector<int> xs;
int main()
{
	int n;
	scanf("%i",&n);
	for(int i=1;i<=n;i++) scanf("%i %i",&x[i],&y[i]),xs.pb(x[i]);
	sort(xs.begin(),xs.end());
	for(int i=1;i<=n;i++) a[x[i]=lower_bound(xs.begin(),xs.end(),x[i])-xs.begin()+1]=y[i],id[i]=i;
	sort(id+1,id+1+n,[&](int i, int j){ return y[i]>y[j];});
	ll sol=0;
	for(int j=1,i;i=id[j],j<=n;j++)
	{
		int pos=x[i];
		int B=pos/S;
		int r=(B+1)*S-1;
		top=0;
		for(int k=r;k>pos;k--) if(use[k])
		{
			while(top && stk[top]>a[k]) top--;
			stk[++top]=a[k];
		}
		int mn=top?stk[1]:1e9+7;
		int ans=0;
		ans+=top;
		for(int k=B+1;k*S<=n;k++)
		{
			if(ptr[k])
			{
				ans+=upper_bound(SEQ[k],SEQ[k]+ptr[k],mn)-SEQ[k];
				mn=min(mn,SEQ[k][0]);
			}
		}
		sol+=ans;
		Add(x[i]);
	}
	printf("%lld\n",sol);
	return 0;
}

Compilation message

scarecrows.cpp: In function 'int main()':
scarecrows.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
scarecrows.cpp:32:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i %i",&x[i],&y[i]),xs.pb(x[i]);
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 504 KB Output is correct
2 Correct 33 ms 760 KB Output is correct
3 Correct 14 ms 632 KB Output is correct
4 Correct 14 ms 632 KB Output is correct
5 Correct 20 ms 760 KB Output is correct
6 Correct 31 ms 636 KB Output is correct
7 Correct 33 ms 632 KB Output is correct
8 Correct 11 ms 636 KB Output is correct
9 Correct 22 ms 632 KB Output is correct
10 Correct 31 ms 760 KB Output is correct
11 Correct 32 ms 632 KB Output is correct
12 Correct 13 ms 504 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 845 ms 8000 KB Output is correct
2 Correct 1812 ms 9292 KB Output is correct
3 Correct 797 ms 9188 KB Output is correct
4 Correct 648 ms 9248 KB Output is correct
5 Correct 926 ms 9156 KB Output is correct
6 Correct 1670 ms 9324 KB Output is correct
7 Correct 1728 ms 9204 KB Output is correct
8 Correct 1799 ms 9196 KB Output is correct
9 Correct 448 ms 9248 KB Output is correct
10 Correct 1345 ms 9196 KB Output is correct
11 Correct 1790 ms 9452 KB Output is correct
12 Correct 1847 ms 9328 KB Output is correct
13 Correct 1821 ms 9408 KB Output is correct
14 Correct 479 ms 9336 KB Output is correct
15 Correct 1796 ms 9196 KB Output is correct
16 Correct 1875 ms 9324 KB Output is correct
17 Correct 890 ms 6256 KB Output is correct
18 Correct 1634 ms 9352 KB Output is correct
19 Correct 1556 ms 9316 KB Output is correct
20 Correct 1564 ms 9340 KB Output is correct