oj.uz

Submission #48784

# Submission time Handle Problem Language Result Execution time Memory
48784 2018-05-18T17:48:16 Z Pajaraja Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 1667 ms 107608 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;
	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(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;
              ~^~~~~~~~~~
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 11 ms 12156 KB Output is correct
2 Correct 17 ms 12388 KB Output is correct
3 Correct 13 ms 12464 KB Output is correct
4 Correct 12 ms 12512 KB Output is correct
5 Correct 16 ms 12512 KB Output is correct
6 Correct 15 ms 12520 KB Output is correct
7 Correct 18 ms 12520 KB Output is correct
8 Correct 14 ms 12544 KB Output is correct
9 Correct 17 ms 12544 KB Output is correct
10 Correct 14 ms 12544 KB Output is correct
11 Correct 16 ms 12544 KB Output is correct
12 Correct 14 ms 12544 KB Output is correct
13 Correct 25 ms 12744 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 14668 KB Output is correct
2 Correct 130 ms 16744 KB Output is correct
3 Correct 208 ms 18932 KB Output is correct
4 Correct 294 ms 20852 KB Output is correct
5 Correct 310 ms 20908 KB Output is correct
6 Correct 383 ms 20908 KB Output is correct
7 Correct 250 ms 20980 KB Output is correct
8 Correct 254 ms 20980 KB Output is correct
9 Correct 152 ms 20980 KB Output is correct
10 Correct 178 ms 20980 KB Output is correct
11 Correct 139 ms 20980 KB Output is correct
12 Correct 180 ms 20980 KB Output is correct
13 Correct 202 ms 20980 KB Output is correct
14 Correct 207 ms 20980 KB Output is correct
15 Correct 178 ms 20980 KB Output is correct
16 Correct 267 ms 20980 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 712 ms 27484 KB Output is correct
2 Correct 1078 ms 34760 KB Output is correct
3 Correct 1341 ms 41004 KB Output is correct
4 Runtime error 1667 ms 107608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -