oj.uz

Submission #48786

# Submission time Handle Problem Language Result Execution time Memory
48786 2018-05-18T17:59:39 Z Pajaraja Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 2000 ms 100644 KB 
#include <bits/stdc++.h>
#define MAXN 1000007
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 20 ms 23928 KB Output is correct
2 Correct 22 ms 24164 KB Output is correct
3 Correct 24 ms 24236 KB Output is correct
4 Correct 22 ms 24296 KB Output is correct
5 Correct 23 ms 24296 KB Output is correct
6 Correct 23 ms 24296 KB Output is correct
7 Correct 22 ms 24296 KB Output is correct
8 Correct 25 ms 24296 KB Output is correct
9 Correct 24 ms 24296 KB Output is correct
10 Correct 23 ms 24296 KB Output is correct
11 Correct 30 ms 24296 KB Output is correct
12 Correct 23 ms 24296 KB Output is correct
13 Correct 25 ms 24296 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 26188 KB Output is correct
2 Correct 111 ms 28360 KB Output is correct
3 Correct 183 ms 30652 KB Output is correct
4 Correct 233 ms 32580 KB Output is correct
5 Correct 233 ms 32612 KB Output is correct
6 Correct 234 ms 32612 KB Output is correct
7 Correct 490 ms 32612 KB Output is correct
8 Correct 271 ms 32892 KB Output is correct
9 Correct 162 ms 32892 KB Output is correct
10 Correct 157 ms 32892 KB Output is correct
11 Correct 149 ms 32892 KB Output is correct
12 Correct 198 ms 32892 KB Output is correct
13 Correct 192 ms 32892 KB Output is correct
14 Correct 209 ms 32892 KB Output is correct
15 Correct 216 ms 32892 KB Output is correct
16 Correct 247 ms 32892 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 757 ms 39260 KB Output is correct
2 Correct 1031 ms 46476 KB Output is correct
3 Correct 1454 ms 52824 KB Output is correct
4 Correct 1690 ms 69840 KB Output is correct
5 Correct 648 ms 69840 KB Output is correct
6 Correct 1721 ms 77488 KB Output is correct
7 Correct 1751 ms 83280 KB Output is correct
8 Correct 1843 ms 89124 KB Output is correct
9 Correct 1752 ms 95048 KB Output is correct
10 Execution timed out 2033 ms 100644 KB Time limit exceeded
11 Halted 0 ms 0 KB -