oj.uz

Submission #65392

# Submission time Handle Problem Language Result Execution time Memory
65392 2018-08-07T13:41:54 Z hamzqq9 Horses (IOI15_horses) C++14
100 / 100
 676 ms 278424 KB 
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define st first
#define nd second
#define orta ((bas+son)>>1)
#define ii pair<int,int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long


struct day {

	int l,r;
	int xpro;
	int mxy;

	day(int a,int b,int c,int d) {

		l=a;r=b;xpro=c;mxy=d;

	}

	bool operator<(const day& oth) const {

		return r<oth.r;

	}

	bool operator>(const day& oth) const {

		return r>oth.r;

	}

};

set<day> S;
int N;
int X[500005];
int seg[500005*4],tut[500005];
int allpro=1;

int fe(int x,int y) {

	int res=1;
	int cur=x;

	while(y) {

		if(y&1) res=1ll*res*cur%MOD;

		y>>=1;

		cur=1ll*cur*cur%MOD;

	}

	return res;

}

int get(int node,int bas,int son,int x,int y) {

	if(bas>=x && son<=y) return seg[node];

	if(orta>=x && orta+1<=y) return max(get(node*2,bas,orta,x,y),get(node*2+1,orta+1,son,x,y));
	if(orta>=x) return get(node*2,bas,orta,x,y);
	if(orta+1<=y) return get(node*2+1,orta+1,son,x,y);

}

void up(int pos,int val) {

	seg[tut[pos]]=val;

	for(int node=tut[pos]>>1;node>=1;node>>=1) {

		seg[node]=max(seg[node<<1],seg[(node<<1)|1]);

	}

}

void build(int node,int bas,int son,int Y[]) {

	if(bas==son) {

		seg[node]=Y[bas];
		tut[bas]=node;

		return ;

	}

	build(node*2,bas,orta,Y);
	build(node*2+1,orta+1,son,Y);

	seg[node]=max(seg[node*2],seg[node*2+1]);

}

int get_ans() {

	vector< ii > v;

	int tot=0;

	auto it=S.rbegin();

	ll mul=1;

	while(1) {

		tot++;

		v.pb({it->xpro,it->mxy});

//		printf("%dth xpro-->%d mxy-->%d\n",tot-1,v.back().st,v.back().nd);

		mul=1ll*mul*it->xpro;

		it++;
		
		if(it==S.rend()) break ;

		if(mul>1e9) break ;

	}

	reverse(all(v));

	int best_ind=0;

	for(int i=0;i<tot;i++) {

		int ind=i;
		ll curpro=1;

		while(i+1<tot) {

			ll val=1ll*v[i+1].st*v[i+1].nd;

			if(val<v[ind].nd && curpro*val<v[ind].nd) {

				curpro*=v[i+1].st;

				i++;

				continue ;

			}

			break ;

		}

		if(i==tot-1) {

			best_ind=ind;

			break ;

		}

	}

	int dv=1;

	for(int i=tot-1;i>best_ind;i--) {

		dv=1ll*dv*v[i].st%MOD;

	}

	return 1ll*fe(dv,MOD-2)*allpro%MOD*v[best_ind].nd%MOD;

}

int init(int N, int X[], int Y[]) {
	
	::N=N;

	for(int i=0;i<N;i++) {

		::X[i]=X[i];

		day cur(i,i,X[i],Y[i]);

		while(i+1<N && X[i+1]==1) {

			i++;

			cur.r=i;
			cur.mxy=max(cur.mxy,Y[i]);

			::X[i]=X[i];

		}

		S.insert(cur);

		allpro=1ll*allpro*cur.xpro%MOD;

	}

	build(1,0,N-1,Y);

	return get_ans();

}

int updateX(int pos, int val) {	
	
	allpro=1ll*allpro*fe(X[pos],MOD-2)%MOD;

	allpro=1ll*allpro*val%MOD;

	if(X[pos]==1 && val!=1) {

		day cur(pos,pos,0,0);

		auto _pos=S.lower_bound(cur);

		cur=*_pos;

		S.erase(_pos);

		day l(cur.l,pos-1,cur.xpro,(cur.l>pos-1?0:get(1,0,N-1,cur.l,pos-1)));
		day r(pos,cur.r,val,get(1,0,N-1,pos,cur.r));

		if(cur.l<=pos) S.insert(l);
		S.insert(r);

	}

	if(X[pos]>1 && val==1) {

		day cur(pos,pos,0,0);

		auto _pos=S.lower_bound(cur);

		if(_pos==S.begin()) {

			cur=*_pos;

			S.erase(_pos);

			cur.xpro=1;

			S.insert(cur);

		}
		else {

			day cur2=*_pos;

			S.erase(_pos--);

			day cur1=*_pos;

			S.erase(_pos);

			day nw(cur1.l,cur2.r,cur1.xpro,max(cur1.mxy,cur2.mxy));

			S.insert(nw);

		}

	}

	if(X[pos]>1 && val>1) {

		day cur(pos,pos,0,0);

		auto _pos=S.lower_bound(cur);

		cur=*_pos;

		S.erase(_pos);

		cur.xpro=val;

		S.insert(cur);

	}

	X[pos]=val;

	return get_ans();

}

int updateY(int pos, int val) {
	
	up(pos,val);

	day cur(pos,pos,0,0);

	auto _pos=S.lower_bound(cur);

	cur=*_pos;

	S.erase(_pos);

	cur.mxy=get(1,0,N-1,cur.l,cur.r);

	S.insert(cur);

	return get_ans();

}

Compilation message

horses.cpp: In function 'int fe(int, int)':
horses.cpp:53:26: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   if(y&1) res=1ll*res*cur%MOD;
                          ^
horses.cpp:57:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   cur=1ll*cur*cur%MOD;
                  ^
horses.cpp: In function 'int get_ans()':
horses.cpp:129:10: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
   if(mul>1e9) break ;
          ^~~
horses.cpp:174:20: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   dv=1ll*dv*v[i].st%MOD;
                    ^
horses.cpp:178:51: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1ll*fe(dv,MOD-2)*allpro%MOD*v[best_ind].nd%MOD;
                                                   ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:182:33: warning: declaration of 'X' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:42:5: note: shadowed declaration is here
 int X[500005];
     ^
horses.cpp:182:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:41:5: note: shadowed declaration is here
 int N;
     ^
horses.cpp:205:29: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   allpro=1ll*allpro*cur.xpro%MOD;
                             ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:217:36: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  allpro=1ll*allpro*fe(X[pos],MOD-2)%MOD;
                                    ^
horses.cpp:219:23: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  allpro=1ll*allpro*val%MOD;
                       ^
horses.cpp: In function 'int get(int, int, int, int, int)':
horses.cpp:73:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 2 ms 564 KB Output is correct
6 Correct 5 ms 568 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Correct 3 ms 568 KB Output is correct
9 Correct 3 ms 700 KB Output is correct
10 Correct 2 ms 700 KB Output is correct
11 Correct 3 ms 700 KB Output is correct
12 Correct 3 ms 700 KB Output is correct
13 Correct 3 ms 700 KB Output is correct
14 Correct 3 ms 700 KB Output is correct
15 Correct 2 ms 700 KB Output is correct
16 Correct 3 ms 700 KB Output is correct
17 Correct 2 ms 700 KB Output is correct
18 Correct 3 ms 700 KB Output is correct
19 Correct 3 ms 700 KB Output is correct
20 Correct 3 ms 732 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 732 KB Output is correct
2 Correct 3 ms 732 KB Output is correct
3 Correct 3 ms 732 KB Output is correct
4 Correct 3 ms 732 KB Output is correct
5 Correct 2 ms 732 KB Output is correct
6 Correct 3 ms 732 KB Output is correct
7 Correct 3 ms 732 KB Output is correct
8 Correct 3 ms 732 KB Output is correct
9 Correct 2 ms 732 KB Output is correct
10 Correct 2 ms 732 KB Output is correct
11 Correct 2 ms 732 KB Output is correct
12 Correct 3 ms 732 KB Output is correct
13 Correct 4 ms 732 KB Output is correct
14 Correct 2 ms 732 KB Output is correct
15 Correct 3 ms 732 KB Output is correct
16 Correct 4 ms 732 KB Output is correct
17 Correct 3 ms 732 KB Output is correct
18 Correct 2 ms 732 KB Output is correct
19 Correct 3 ms 732 KB Output is correct
20 Correct 3 ms 732 KB Output is correct
21 Correct 3 ms 732 KB Output is correct
22 Correct 2 ms 732 KB Output is correct
23 Correct 5 ms 732 KB Output is correct
24 Correct 4 ms 732 KB Output is correct
25 Correct 5 ms 732 KB Output is correct
26 Correct 5 ms 796 KB Output is correct
27 Correct 7 ms 796 KB Output is correct
28 Correct 5 ms 840 KB Output is correct
29 Correct 5 ms 840 KB Output is correct
30 Correct 4 ms 900 KB Output is correct
31 Correct 4 ms 900 KB Output is correct
32 Correct 7 ms 900 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 45220 KB Output is correct
2 Correct 650 ms 57824 KB Output is correct
3 Correct 617 ms 61484 KB Output is correct
4 Correct 613 ms 69128 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 69128 KB Output is correct
2 Correct 3 ms 69128 KB Output is correct
3 Correct 4 ms 69128 KB Output is correct
4 Correct 2 ms 69128 KB Output is correct
5 Correct 3 ms 69128 KB Output is correct
6 Correct 3 ms 69128 KB Output is correct
7 Correct 4 ms 69128 KB Output is correct
8 Correct 4 ms 69128 KB Output is correct
9 Correct 2 ms 69128 KB Output is correct
10 Correct 3 ms 69128 KB Output is correct
11 Correct 2 ms 69128 KB Output is correct
12 Correct 3 ms 69128 KB Output is correct
13 Correct 3 ms 69128 KB Output is correct
14 Correct 2 ms 69128 KB Output is correct
15 Correct 3 ms 69128 KB Output is correct
16 Correct 3 ms 69128 KB Output is correct
17 Correct 2 ms 69128 KB Output is correct
18 Correct 2 ms 69128 KB Output is correct
19 Correct 3 ms 69128 KB Output is correct
20 Correct 3 ms 69128 KB Output is correct
21 Correct 4 ms 69128 KB Output is correct
22 Correct 3 ms 69128 KB Output is correct
23 Correct 4 ms 69128 KB Output is correct
24 Correct 4 ms 69128 KB Output is correct
25 Correct 4 ms 69128 KB Output is correct
26 Correct 5 ms 69128 KB Output is correct
27 Correct 5 ms 69128 KB Output is correct
28 Correct 5 ms 69128 KB Output is correct
29 Correct 3 ms 69128 KB Output is correct
30 Correct 4 ms 69128 KB Output is correct
31 Correct 7 ms 69128 KB Output is correct
32 Correct 6 ms 69128 KB Output is correct
33 Correct 69 ms 69128 KB Output is correct
34 Correct 50 ms 69128 KB Output is correct
35 Correct 318 ms 87332 KB Output is correct
36 Correct 294 ms 97960 KB Output is correct
37 Correct 56 ms 97960 KB Output is correct
38 Correct 174 ms 97960 KB Output is correct
39 Correct 35 ms 97960 KB Output is correct
40 Correct 279 ms 111096 KB Output is correct
41 Correct 41 ms 111096 KB Output is correct
42 Correct 48 ms 111096 KB Output is correct
43 Correct 252 ms 121508 KB Output is correct
44 Correct 255 ms 127912 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 127912 KB Output is correct
2 Correct 3 ms 127912 KB Output is correct
3 Correct 3 ms 127912 KB Output is correct
4 Correct 2 ms 127912 KB Output is correct
5 Correct 3 ms 127912 KB Output is correct
6 Correct 3 ms 127912 KB Output is correct
7 Correct 4 ms 127912 KB Output is correct
8 Correct 2 ms 127912 KB Output is correct
9 Correct 3 ms 127912 KB Output is correct
10 Correct 2 ms 127912 KB Output is correct
11 Correct 3 ms 127912 KB Output is correct
12 Correct 3 ms 127912 KB Output is correct
13 Correct 3 ms 127912 KB Output is correct
14 Correct 2 ms 127912 KB Output is correct
15 Correct 3 ms 127912 KB Output is correct
16 Correct 3 ms 127912 KB Output is correct
17 Correct 3 ms 127912 KB Output is correct
18 Correct 2 ms 127912 KB Output is correct
19 Correct 2 ms 127912 KB Output is correct
20 Correct 2 ms 127912 KB Output is correct
21 Correct 3 ms 127912 KB Output is correct
22 Correct 2 ms 127912 KB Output is correct
23 Correct 4 ms 127912 KB Output is correct
24 Correct 3 ms 127912 KB Output is correct
25 Correct 5 ms 127912 KB Output is correct
26 Correct 5 ms 127912 KB Output is correct
27 Correct 5 ms 127912 KB Output is correct
28 Correct 5 ms 127912 KB Output is correct
29 Correct 4 ms 127912 KB Output is correct
30 Correct 5 ms 127912 KB Output is correct
31 Correct 4 ms 127912 KB Output is correct
32 Correct 5 ms 127912 KB Output is correct
33 Correct 519 ms 132972 KB Output is correct
34 Correct 676 ms 145544 KB Output is correct
35 Correct 627 ms 149300 KB Output is correct
36 Correct 584 ms 156864 KB Output is correct
37 Correct 51 ms 156864 KB Output is correct
38 Correct 57 ms 156864 KB Output is correct
39 Correct 303 ms 174800 KB Output is correct
40 Correct 301 ms 185516 KB Output is correct
41 Correct 47 ms 185516 KB Output is correct
42 Correct 161 ms 185516 KB Output is correct
43 Correct 44 ms 185516 KB Output is correct
44 Correct 274 ms 198524 KB Output is correct
45 Correct 49 ms 198524 KB Output is correct
46 Correct 49 ms 198524 KB Output is correct
47 Correct 266 ms 208996 KB Output is correct
48 Correct 265 ms 215396 KB Output is correct
49 Correct 225 ms 215396 KB Output is correct
50 Correct 270 ms 215396 KB Output is correct
51 Correct 476 ms 238404 KB Output is correct
52 Correct 401 ms 249744 KB Output is correct
53 Correct 254 ms 249744 KB Output is correct
54 Correct 290 ms 249744 KB Output is correct
55 Correct 123 ms 249744 KB Output is correct
56 Correct 356 ms 267040 KB Output is correct
57 Correct 228 ms 267040 KB Output is correct
58 Correct 200 ms 267040 KB Output is correct
59 Correct 283 ms 278424 KB Output is correct