oj.uz

Submission #48788

# Submission time Handle Problem Language Result Execution time Memory
48788 2018-05-18T18:04:32 Z Pajaraja Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 2000 ms 50912 KB 
#include <bits/stdc++.h>
#define MAXN 200007
using namespace std;
map<int,int> m;
vector<int> zh,aq[MAXN];
int a[2][MAXN],t[MAXN],seg[12*MAXN],bit[3*MAXN+7],lf[MAXN];
void upd(int l,int r,int v,int val,int ind)
{
	if(l==r) {seg[ind]=val; return;}
	int s=(l+r)/2;
	if(s>=v) upd(l,s,v,val,2*ind);
	else upd(s+1,r,v,val,2*ind+1);
	seg[ind]=max(seg[2*ind],seg[2*ind+1]);
}
int nmax(int l,int r,int lt,int rt,int ind)
{
	if(l>r) return 0;
	if(l>=lt  && r<=rt) return seg[ind];
	if(r<lt || l>rt) return 0;
	int s=(l+r)/2;
	return max(nmax(l,s,lt,rt,2*ind),nmax(s+1,r,lt,rt,2*ind+1));
}
void updf(int ind) {for(int i=ind;i<=3*MAXN;i+=(i&-i)) bit[i]++;}
int fval(int ind) 
{
	int sol=0;
	for(int i=ind;i>0;i-=(i&-i)) sol+=bit[i];
	return sol;
}
int main()
{
	int n,k;
	long long sol=0;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++) {scanf("%d%d",&a[0][i],&a[1][i]); zh.push_back(a[0][i]); zh.push_back(a[1][i]);}
	for(int i=1;i<=k;i++) {scanf("%d",&t[i]); zh.push_back(t[i]);}
	sort(zh.begin(),zh.end());
	int sz=zh.size();
	for(int i=0;i<zh.size();i++) m[zh[i]]=i;
	for(int i=1;i<=k;i++) upd(0,sz,m[t[i]],i,1);
	for(int i=0;i<n;i++) lf[i]=nmax(0,sz,m[min(a[0][i],a[1][i])],m[max(a[0][i],a[1][i])]-1,1);
	for(int i=0;i<n;i++) aq[lf[i]].push_back(i);
	for(int i=k;i>=1;i--)
	{
		updf(m[t[i]]+1);
		for(int j=0;j<aq[i].size();j++)
		{
			int b=min(a[0][aq[i][j]],a[1][aq[i][j]]),c=max(a[0][aq[i][j]],a[1][aq[i][j]]);
			if((fval(3*MAXN)-fval(m[c]))%2==0) sol+=c;
			else sol+=b; 
		}
	}
	for(int j=0;j<aq[0].size();j++)
	{
		int b=a[0][aq[0][j]],c=a[1][aq[0][j]];
		if((fval(3*MAXN)-fval(m[c]))%2==0) sol+=b;
		else sol+=c;
	}
	printf("%lld",sol);
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:39:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<zh.size();i++) m[zh[i]]=i;
              ~^~~~~~~~~~
fortune_telling2.cpp:46:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<aq[i].size();j++)
               ~^~~~~~~~~~~~~
fortune_telling2.cpp:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<aq[0].size();j++)
              ~^~~~~~~~~~~~~
fortune_telling2.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:35:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<n;i++) {scanf("%d%d",&a[0][i],&a[1][i]); zh.push_back(a[0][i]); zh.push_back(a[1][i]);}
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:36:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=k;i++) {scanf("%d",&t[i]); zh.push_back(t[i]);}
                         ~~~~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5240 KB Output is correct
2 Correct 8 ms 5352 KB Output is correct
3 Correct 9 ms 5416 KB Output is correct
4 Correct 11 ms 5468 KB Output is correct
5 Correct 8 ms 5512 KB Output is correct
6 Correct 9 ms 5512 KB Output is correct
7 Correct 8 ms 5540 KB Output is correct
8 Correct 9 ms 5540 KB Output is correct
9 Correct 9 ms 5540 KB Output is correct
10 Correct 8 ms 5540 KB Output is correct
11 Correct 9 ms 5540 KB Output is correct
12 Correct 8 ms 5540 KB Output is correct
13 Correct 9 ms 5540 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 7456 KB Output is correct
2 Correct 119 ms 9528 KB Output is correct
3 Correct 204 ms 11976 KB Output is correct
4 Correct 290 ms 13764 KB Output is correct
5 Correct 282 ms 13896 KB Output is correct
6 Correct 287 ms 13896 KB Output is correct
7 Correct 280 ms 13896 KB Output is correct
8 Correct 269 ms 13896 KB Output is correct
9 Correct 169 ms 13896 KB Output is correct
10 Correct 155 ms 13896 KB Output is correct
11 Correct 144 ms 13896 KB Output is correct
12 Correct 155 ms 13896 KB Output is correct
13 Correct 168 ms 13896 KB Output is correct
14 Correct 193 ms 13896 KB Output is correct
15 Correct 166 ms 13896 KB Output is correct
16 Correct 239 ms 13896 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 20440 KB Output is correct
2 Correct 892 ms 27864 KB Output is correct
3 Correct 1121 ms 34008 KB Output is correct
4 Correct 1774 ms 50896 KB Output is correct
5 Correct 549 ms 50896 KB Output is correct
6 Execution timed out 2065 ms 50912 KB Time limit exceeded
7 Halted 0 ms 0 KB -