oj.uz

Submission #48783

# Submission time Handle Problem Language Result Execution time Memory
48783 2018-05-18T17:45:34 Z Pajaraja Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 1583 ms 107488 KB 
#include <bits/stdc++.h>
#define MAXN 500007
using namespace std;
map<int,int> m;
vector<int> zh,aq[MAXN];
int a[2][MAXN],t[MAXN],seg[4*MAXN],bit[4*MAXN],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<=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+1;
	for(int i=1;i<=k;i++) upd(1,sz,m[t[i]],i,1);
	for(int i=0;i<n;i++) lf[i]=nmax(1,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(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(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+1;
              ~^~~~~~~~~~
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 13 ms 12152 KB Output is correct
2 Correct 14 ms 12260 KB Output is correct
3 Correct 14 ms 12312 KB Output is correct
4 Correct 15 ms 12440 KB Output is correct
5 Correct 15 ms 12440 KB Output is correct
6 Correct 14 ms 12564 KB Output is correct
7 Correct 15 ms 12564 KB Output is correct
8 Correct 14 ms 12604 KB Output is correct
9 Correct 14 ms 12604 KB Output is correct
10 Correct 15 ms 12604 KB Output is correct
11 Correct 12 ms 12604 KB Output is correct
12 Correct 14 ms 12604 KB Output is correct
13 Correct 15 ms 12604 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 14412 KB Output is correct
2 Correct 139 ms 16636 KB Output is correct
3 Correct 194 ms 18892 KB Output is correct
4 Correct 293 ms 20920 KB Output is correct
5 Correct 286 ms 20920 KB Output is correct
6 Correct 264 ms 20940 KB Output is correct
7 Correct 274 ms 20956 KB Output is correct
8 Correct 255 ms 21092 KB Output is correct
9 Correct 173 ms 21092 KB Output is correct
10 Correct 166 ms 21092 KB Output is correct
11 Correct 150 ms 21092 KB Output is correct
12 Correct 184 ms 21092 KB Output is correct
13 Correct 153 ms 21092 KB Output is correct
14 Correct 178 ms 21092 KB Output is correct
15 Correct 230 ms 21092 KB Output is correct
16 Correct 298 ms 21092 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 732 ms 27416 KB Output is correct
2 Correct 995 ms 34792 KB Output is correct
3 Correct 1307 ms 41064 KB Output is correct
4 Runtime error 1583 ms 107488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -