oj.uz

Submission #205685

# Submission time Handle Problem Language Result Execution time Memory
205685 2020-02-29T13:33:58 Z GioChkhaidze Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 7 ms 632 KB 
#include <bits/stdc++.h>
#define Tree int h,int l,int r
#define Left (h<<1),l,(l+r)>>1
#define Right ((h<<1)|1),((l+r)>>1)+1,r
#define ll long long
#define pb push_back
#define F first
#define S second
using namespace std;
const int Nm=1005;
ll ans;
int n,q,L,R,S;
int l[Nm],r[Nm],t[Nm];
int G[3*Nm],Last[3*Nm],Rf[3*Nm],v[12*Nm];
pair < int , int > Id[Nm];
vector < int > s;
map < int , int > f;

void Build(Tree) {
	if (l==r) { v[h]=Last[l]; return ;}
	Build(Left),Build(Right);
	v[h]=max(v[(h<<1)],v[((h<<1)|1)]);
}

int Get(Tree) {
	if (r<L || R<l) return 0;
	if (L<=l && r<=R) return v[h];
	int x=Get(Left),y=Get(Right);
	return max(x,y);
}

void Up(int x) {
	while (x<=S) {
		G[x]++;
		x+=(x & -x);
	}
}

int Ge(int x) {
	int res=0;
	while (x>0) {
		res+=G[x];
		x-=(x & -x);
	}
	return res;
}

main () {
	scanf("%d%d",&n,&q);
	for (int i=1; i<=n; i++) {
		scanf("%d%d",&l[i],&r[i]);
		s.pb(l[i]),s.pb(r[i]);
	}
	
	for (int i=1; i<=q; i++) {
		scanf("%d",&t[i]);
		s.pb(t[i]);
	}
	
	sort(s.begin(),s.end());
	s.erase(unique(s.begin(),s.end()),s.end());
	
	for (int i=0; i<s.size(); i++) f[s[i]]=i+1,Rf[i+1]=s[i];
	for (int i=1; i<=n; i++) l[i]=f[l[i]],r[i]=f[r[i]];
	for (int i=1; i<=q; i++) t[i]=f[t[i]];
	
	S=s.size();
	
	for (int i=1; i<=q; i++) Last[t[i]]=i;
	Build(1,1,S);
	
	for (int i=1; i<=n; i++) {
		L=min(l[i],r[i]),R=max(l[i],r[i])-1;
		Id[i].F=Get(1,1,S),Id[i].S=i;
	}
	
	sort(Id+1,Id+n+1);
	
	int Q=q,tot=0;
	for (int i=n; i>=1; i--) {
		while (Q && Id[i].F<Q) Up(t[Q]),--Q;
		tot=Ge(S)-Ge(max(l[Id[i].S],r[Id[i].S])-1);
		
		if (Id[i].F && l[Id[i].S]<r[Id[i].S]) 
			swap(l[Id[i].S],r[Id[i].S]);

		if (tot%2) 
			ans+=Rf[r[Id[i].S]];
				else 
			ans+=Rf[l[Id[i].S]];
	}	
	
	cout<<ans<<endl;
}

Compilation message

fortune_telling2.cpp:48:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:63:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<s.size(); i++) f[s[i]]=i+1,Rf[i+1]=s[i];
                ~^~~~~~~~~
fortune_telling2.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&q);
  ~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&l[i],&r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 7 ms 508 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 7 ms 504 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 7 ms 632 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 6 ms 504 KB Output is correct
12 Correct 6 ms 504 KB Output is correct
13 Correct 6 ms 504 KB Output is correct
14 Execution timed out 7 ms 376 KB Time limit exceeded (wall clock)
15 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 7 ms 508 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 7 ms 504 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 7 ms 632 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 6 ms 504 KB Output is correct
12 Correct 6 ms 504 KB Output is correct
13 Correct 6 ms 504 KB Output is correct
14 Execution timed out 7 ms 376 KB Time limit exceeded (wall clock)
15 Halted 0 ms 0 KB -