oj.uz

Submission #554727

# Submission time Handle Problem Language Result Execution time Memory
554727 2022-04-29T09:53:51 Z cheetose Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 453 ms 63744 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 987654321987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a))
#define MEM_1(a) memset((a),-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define COMPRESS(a) sort(ALL(a));a.resize(unique(ALL(a))-a.begin())
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ld, ld> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<ld> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const int MOD = 998244353;
ll POW(ll a, ll b, ll MMM = MOD) { ll ret = 1; for (; b; b >>= 1, a = (a*a) % MMM)if (b & 1)ret = (ret*a) % MMM; return ret; }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };
int ddx[] = { -1,-2,1,-2,2,-1,2,1 }, ddy[] = { -2,-1,-2,1,-1,2,1,2 };

int a[200000],b[200000],t[200000],rev[200000];
Vi v[600000],q[600000];
int tree[1<<21];
int mx[600000];
void init(int node,int S,int E){
	if(S==E){
		tree[node]=mx[S];
		return;
	}
	int L=node<<1,R=L|1,M=S+E>>1;
	init(L,S,M);
	init(R,M+1,E);
	tree[node]=max(tree[L],tree[R]);
}
int find(int node,int S,int E,int i,int j){
	if(i>E || j<S)return -1;
	if(i<=S && j>=E)return tree[node];
	int L=node<<1,R=L|1,M=S+E>>1;
	return max(find(L,S,M,i,j),find(R,M+1,E,i,j));
}

int T[200005];
int n,m;
void upd(int i,int k){
	i++;
	while(i<=m){
		T[i]+=k;
		i+=(i&-i);
	}
}
int sum(int i){
	i++;
	int c=0;
	while(i>0){
		c+=T[i];
		i-=(i&-i);
	}
	return c;
}
int sum(int i,int j){
	return sum(j)-sum(i-1);
}
int main(){
	MEM_1(mx);
	Vi vv;
	scanf("%d%d",&n,&m);
	fup(i,0,n-1,1){
		scanf("%d%d",a+i,b+i);
		vv.pb(a[i]);vv.pb(b[i]);
		if(a[i]>b[i])swap(a[i],b[i]);
		else rev[i]=1;
	}
	fup(i,0,m-1,1){
		scanf("%d",t+i);
		vv.pb(t[i]);
	}
	COMPRESS(vv);
	int N=vv.size();
	fup(i,0,n-1,1){
		a[i]=lower_bound(ALL(vv),a[i])-vv.begin(),b[i]=lower_bound(ALL(vv),b[i])-vv.begin();
		q[b[i]].pb(i);
	}
	fup(i,0,m-1,1){
		t[i]=lower_bound(ALL(vv),t[i])-vv.begin();
		v[t[i]].pb(i);
		mx[t[i]]=i;
	}
	init(1,0,N-1);
	ll ans=0;
	fdn(k,N-1,0,1){
		for(int x:v[k])upd(x,1);
		for(int i:q[k]){
			int r=find(1,0,N-1,a[i],b[i]-1);
			int d;
			if(r==-1)d=sum(0,m-1)+rev[i];
			else d=sum(r+1,m-1);
			if(d&1)ans+=vv[a[i]];
			else ans+=vv[b[i]];
		}
	}
	printf("%lld\n",ans);
}

Compilation message

fortune_telling2.cpp: In function 'void init(int, int, int)':
fortune_telling2.cpp:52:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |  int L=node<<1,R=L|1,M=S+E>>1;
      |                        ~^~
fortune_telling2.cpp: In function 'int find(int, int, int, int, int)':
fortune_telling2.cpp:60:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |  int L=node<<1,R=L|1,M=S+E>>1;
      |                        ~^~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
fortune_telling2.cpp:89:2: note: in expansion of macro 'fup'
   89 |  fup(i,0,n-1,1){
      |  ^~~
fortune_telling2.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
fortune_telling2.cpp:95:2: note: in expansion of macro 'fup'
   95 |  fup(i,0,m-1,1){
      |  ^~~
fortune_telling2.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
fortune_telling2.cpp:101:2: note: in expansion of macro 'fup'
  101 |  fup(i,0,n-1,1){
      |  ^~~
fortune_telling2.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
fortune_telling2.cpp:105:2: note: in expansion of macro 'fup'
  105 |  fup(i,0,m-1,1){
      |  ^~~
fortune_telling2.cpp:11:30: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   11 | #define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
      |                              ^
fortune_telling2.cpp:112:2: note: in expansion of macro 'fdn'
  112 |  fdn(k,N-1,0,1){
      |  ^~~
fortune_telling2.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   scanf("%d%d",a+i,b+i);
      |   ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   scanf("%d",t+i);
      |   ~~~~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 30932 KB Output is correct
2 Correct 17 ms 30852 KB Output is correct
3 Correct 20 ms 30956 KB Output is correct
4 Correct 17 ms 30996 KB Output is correct
5 Correct 17 ms 30932 KB Output is correct
6 Correct 17 ms 31012 KB Output is correct
7 Correct 17 ms 30932 KB Output is correct
8 Correct 18 ms 30888 KB Output is correct
9 Correct 16 ms 30932 KB Output is correct
10 Correct 17 ms 30872 KB Output is correct
11 Correct 18 ms 30940 KB Output is correct
12 Correct 16 ms 30992 KB Output is correct
13 Correct 18 ms 31012 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 30932 KB Output is correct
2 Correct 17 ms 30852 KB Output is correct
3 Correct 20 ms 30956 KB Output is correct
4 Correct 17 ms 30996 KB Output is correct
5 Correct 17 ms 30932 KB Output is correct
6 Correct 17 ms 31012 KB Output is correct
7 Correct 17 ms 30932 KB Output is correct
8 Correct 18 ms 30888 KB Output is correct
9 Correct 16 ms 30932 KB Output is correct
10 Correct 17 ms 30872 KB Output is correct
11 Correct 18 ms 30940 KB Output is correct
12 Correct 16 ms 30992 KB Output is correct
13 Correct 18 ms 31012 KB Output is correct
14 Correct 28 ms 32252 KB Output is correct
15 Correct 46 ms 33716 KB Output is correct
16 Correct 64 ms 35576 KB Output is correct
17 Correct 82 ms 36696 KB Output is correct
18 Correct 79 ms 36740 KB Output is correct
19 Correct 77 ms 36800 KB Output is correct
20 Correct 78 ms 36712 KB Output is correct
21 Correct 76 ms 36776 KB Output is correct
22 Correct 59 ms 36068 KB Output is correct
23 Correct 59 ms 35464 KB Output is correct
24 Correct 58 ms 35380 KB Output is correct
25 Correct 59 ms 36072 KB Output is correct
26 Correct 62 ms 36292 KB Output is correct
27 Correct 70 ms 36796 KB Output is correct
28 Correct 64 ms 36724 KB Output is correct
29 Correct 72 ms 36704 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 30932 KB Output is correct
2 Correct 17 ms 30852 KB Output is correct
3 Correct 20 ms 30956 KB Output is correct
4 Correct 17 ms 30996 KB Output is correct
5 Correct 17 ms 30932 KB Output is correct
6 Correct 17 ms 31012 KB Output is correct
7 Correct 17 ms 30932 KB Output is correct
8 Correct 18 ms 30888 KB Output is correct
9 Correct 16 ms 30932 KB Output is correct
10 Correct 17 ms 30872 KB Output is correct
11 Correct 18 ms 30940 KB Output is correct
12 Correct 16 ms 30992 KB Output is correct
13 Correct 18 ms 31012 KB Output is correct
14 Correct 28 ms 32252 KB Output is correct
15 Correct 46 ms 33716 KB Output is correct
16 Correct 64 ms 35576 KB Output is correct
17 Correct 82 ms 36696 KB Output is correct
18 Correct 79 ms 36740 KB Output is correct
19 Correct 77 ms 36800 KB Output is correct
20 Correct 78 ms 36712 KB Output is correct
21 Correct 76 ms 36776 KB Output is correct
22 Correct 59 ms 36068 KB Output is correct
23 Correct 59 ms 35464 KB Output is correct
24 Correct 58 ms 35380 KB Output is correct
25 Correct 59 ms 36072 KB Output is correct
26 Correct 62 ms 36292 KB Output is correct
27 Correct 70 ms 36796 KB Output is correct
28 Correct 64 ms 36724 KB Output is correct
29 Correct 72 ms 36704 KB Output is correct
30 Correct 143 ms 44144 KB Output is correct
31 Correct 211 ms 49004 KB Output is correct
32 Correct 285 ms 52584 KB Output is correct
33 Correct 438 ms 63496 KB Output is correct
34 Correct 125 ms 43384 KB Output is correct
35 Correct 453 ms 63644 KB Output is correct
36 Correct 449 ms 63644 KB Output is correct
37 Correct 452 ms 63608 KB Output is correct
38 Correct 431 ms 63548 KB Output is correct
39 Correct 431 ms 63744 KB Output is correct
40 Correct 401 ms 63356 KB Output is correct
41 Correct 436 ms 63660 KB Output is correct
42 Correct 429 ms 63592 KB Output is correct
43 Correct 276 ms 63100 KB Output is correct
44 Correct 264 ms 62820 KB Output is correct
45 Correct 273 ms 62780 KB Output is correct
46 Correct 277 ms 55936 KB Output is correct
47 Correct 253 ms 53044 KB Output is correct
48 Correct 351 ms 59700 KB Output is correct
49 Correct 335 ms 59612 KB Output is correct