oj.uz

Submission #340277

# Submission time Handle Problem Language Result Execution time Memory
340277 2020-12-27T11:26:51 Z AmineWeslati Horses (IOI15_horses) C++14
100 / 100
 1400 ms 131436 KB 
//Never stop trying
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")*/
#include "bits/stdc++.h"
#ifndef LOCAL
#include "horses.h"
#endif
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef string str;
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<str> vs;
typedef vector<ld> vd;
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)

const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int MX = 5e5 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
//constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

ll random(ll a, ll b){
    return a + rng() % (b - a + 1);
}

#ifndef LOCAL  
#define cerr if(false) cerr
#endif
#define dbg(x) cerr << #x << " : " << x << endl; 
#define dbgs(x,y) cerr << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << #v << " : " << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;
#define here() cerr << "here" << endl;

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

/*int modpow(int x, int p){
	if(p==0) return 1;
	ll v=modpow(x,p/2);
	v*=v; v%=MOD;
	if(p%2==1) v*=x,v%=MOD;
	return v; 
}
int cnvrt(ld x){
	int v=x;
	ll ans=modpow(10,v);
	ld r=x-v;
	ans*=(ll)(pow(10,r)+0.5);
	ans%=MOD;
	return ans;
}*/

int N,X[MX],Y[MX];

struct node{
	ld lazy=0,mx=0; 
	int idx=-1;
};

V<node> t(MX*4);
void push_down(int pos){
	t[pos*2].lazy+=t[pos].lazy;
	t[pos*2+1].lazy+=t[pos].lazy;
	t[pos*2].mx+=t[pos].lazy;
	t[pos*2+1].mx+=t[pos].lazy;
	t[pos].lazy=0;
}
void upd(int l, int r, ld val, int pos=1, int tl=0, int tr=N-1){
	if(l>r) return;
	if(l==tl && r==tr){
		t[pos].mx+=val;
		t[pos].lazy+=val;
		if(l==r) t[pos].idx=l;
		return;
	}
	push_down(pos);
	int tm=(tl+tr)/2;
	upd(l,min(r,tm),val,pos*2,tl,tm);
	upd(max(l,tm+1),r,val,pos*2+1,tm+1,tr);
	if(t[pos*2].mx>=t[pos*2+1].mx){
		t[pos].mx=t[pos*2].mx;
		t[pos].idx=t[pos*2].idx;
	}
	else{
		t[pos].mx=t[pos*2+1].mx;
		t[pos].idx=t[pos*2+1].idx;
	}
}

V<ll> t2(MX*4,0);
void upd2(int i, int val, int pos=1, int tl=0, int tr=N-1){
	if(tl==tr){
		t2[pos]=val;
		return;
	}
	int tm=(tl+tr)/2;
	if(i<=tm) upd2(i,val,pos*2,tl,tm);
	else upd2(i,val,pos*2+1,tm+1,tr);
	t2[pos]=(t2[pos*2]*t2[pos*2+1])%MOD;
}

ll get(int l, int r, int pos=1, int tl=0, int tr=N-1){
	if(l>r) return 1;
	if(l==tl && r==tr){
		return t2[pos];
	}
	int tm=(tl+tr)/2;
	return (get(l,min(r,tm),pos*2,tl,tm)*
		get(max(l,tm+1),r,pos*2+1,tm+1,tr))%MOD;

}


int init(int NN, int XX[], int YY[]) {
	N=NN; FOR(i,0,N) X[i]=XX[i],Y[i]=YY[i];
	FOR(i,0,N){
		upd(i,i,log10((ld)Y[i]));
	}
	FOR(i,0,N){
		upd2(i,X[i]);
		upd(i,N-1,log10((ld)X[i]));
	}
	return (get(0,t[1].idx)*Y[t[1].idx])%MOD;
}

int updateX(int pos, int val) {	
	upd(pos,N-1,log10((ld)val)-log10((ld)X[pos]));
	upd2(pos,val);
	X[pos]=val;
	return (get(0,t[1].idx)*Y[t[1].idx])%MOD;
}

int updateY(int pos, int val) {
	upd(pos,pos,log10((ld)val)-log10((ld)Y[pos]));
	Y[pos]=val;
	return (get(0,t[1].idx)*Y[t[1].idx])%MOD;
}

//613988856

#ifdef LOCAL
int main() {
    boost; IO();

    int N; cin>>N;
    int x[N],y[N]; 
    FOR(i,0,N) cin>>x[i];
    FOR(i,0,N) cin>>y[i];
    cout << init(N,x,y) << endl;

    

    return 0;
}
#endif



/* Careful!!!
    .Array bounds
    .Infinite loops
    .Uninitialized variables / empty containers
    .Multisets are shit

   Some insights:
    .Binary search
    .Graph representation
    .Write brute force code
    .Change your approach
*/

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:154:38: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  154 |  return (get(0,t[1].idx)*Y[t[1].idx])%MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:161:38: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  161 |  return (get(0,t[1].idx)*Y[t[1].idx])%MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:167:38: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  167 |  return (get(0,t[1].idx)*Y[t[1].idx])%MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 109932 KB Output is correct
2 Correct 66 ms 109932 KB Output is correct
3 Correct 66 ms 109932 KB Output is correct
4 Correct 69 ms 109932 KB Output is correct
5 Correct 66 ms 109932 KB Output is correct
6 Correct 67 ms 109932 KB Output is correct
7 Correct 66 ms 109932 KB Output is correct
8 Correct 67 ms 109932 KB Output is correct
9 Correct 68 ms 109932 KB Output is correct
10 Correct 66 ms 109932 KB Output is correct
11 Correct 66 ms 109932 KB Output is correct
12 Correct 67 ms 109932 KB Output is correct
13 Correct 66 ms 109932 KB Output is correct
14 Correct 66 ms 109932 KB Output is correct
15 Correct 67 ms 109932 KB Output is correct
16 Correct 67 ms 109932 KB Output is correct
17 Correct 68 ms 109932 KB Output is correct
18 Correct 67 ms 109932 KB Output is correct
19 Correct 66 ms 109932 KB Output is correct
20 Correct 66 ms 110060 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 109932 KB Output is correct
2 Correct 66 ms 109932 KB Output is correct
3 Correct 67 ms 109932 KB Output is correct
4 Correct 67 ms 109952 KB Output is correct
5 Correct 66 ms 109932 KB Output is correct
6 Correct 68 ms 110060 KB Output is correct
7 Correct 67 ms 109932 KB Output is correct
8 Correct 68 ms 109932 KB Output is correct
9 Correct 66 ms 109932 KB Output is correct
10 Correct 67 ms 109932 KB Output is correct
11 Correct 68 ms 109932 KB Output is correct
12 Correct 67 ms 109932 KB Output is correct
13 Correct 67 ms 109932 KB Output is correct
14 Correct 67 ms 109932 KB Output is correct
15 Correct 69 ms 109916 KB Output is correct
16 Correct 67 ms 109932 KB Output is correct
17 Correct 67 ms 109932 KB Output is correct
18 Correct 67 ms 109932 KB Output is correct
19 Correct 67 ms 109932 KB Output is correct
20 Correct 70 ms 109932 KB Output is correct
21 Correct 66 ms 109932 KB Output is correct
22 Correct 68 ms 109932 KB Output is correct
23 Correct 69 ms 109932 KB Output is correct
24 Correct 69 ms 109932 KB Output is correct
25 Correct 68 ms 109932 KB Output is correct
26 Correct 69 ms 109932 KB Output is correct
27 Correct 69 ms 109932 KB Output is correct
28 Correct 69 ms 109932 KB Output is correct
29 Correct 70 ms 109932 KB Output is correct
30 Correct 70 ms 110160 KB Output is correct
31 Correct 68 ms 109932 KB Output is correct
32 Correct 69 ms 109932 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1229 ms 118764 KB Output is correct
2 Correct 1362 ms 130924 KB Output is correct
3 Correct 1335 ms 122476 KB Output is correct
4 Correct 1387 ms 126444 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 109932 KB Output is correct
2 Correct 66 ms 109932 KB Output is correct
3 Correct 67 ms 109932 KB Output is correct
4 Correct 67 ms 109932 KB Output is correct
5 Correct 66 ms 109932 KB Output is correct
6 Correct 66 ms 109932 KB Output is correct
7 Correct 66 ms 109932 KB Output is correct
8 Correct 69 ms 110060 KB Output is correct
9 Correct 67 ms 109932 KB Output is correct
10 Correct 66 ms 109932 KB Output is correct
11 Correct 68 ms 110060 KB Output is correct
12 Correct 67 ms 109932 KB Output is correct
13 Correct 67 ms 109932 KB Output is correct
14 Correct 66 ms 109932 KB Output is correct
15 Correct 68 ms 109960 KB Output is correct
16 Correct 66 ms 109932 KB Output is correct
17 Correct 66 ms 109932 KB Output is correct
18 Correct 69 ms 109932 KB Output is correct
19 Correct 69 ms 110060 KB Output is correct
20 Correct 67 ms 109932 KB Output is correct
21 Correct 67 ms 109932 KB Output is correct
22 Correct 67 ms 109932 KB Output is correct
23 Correct 68 ms 110060 KB Output is correct
24 Correct 70 ms 109932 KB Output is correct
25 Correct 69 ms 109932 KB Output is correct
26 Correct 68 ms 109932 KB Output is correct
27 Correct 70 ms 109932 KB Output is correct
28 Correct 69 ms 109932 KB Output is correct
29 Correct 70 ms 109932 KB Output is correct
30 Correct 69 ms 109932 KB Output is correct
31 Correct 69 ms 110188 KB Output is correct
32 Correct 70 ms 109932 KB Output is correct
33 Correct 1172 ms 117868 KB Output is correct
34 Correct 1163 ms 121740 KB Output is correct
35 Correct 1154 ms 128748 KB Output is correct
36 Correct 1158 ms 128636 KB Output is correct
37 Correct 1124 ms 119916 KB Output is correct
38 Correct 1151 ms 120940 KB Output is correct
39 Correct 1122 ms 119868 KB Output is correct
40 Correct 1136 ms 123756 KB Output is correct
41 Correct 1124 ms 119944 KB Output is correct
42 Correct 1112 ms 120028 KB Output is correct
43 Correct 1107 ms 124184 KB Output is correct
44 Correct 1149 ms 124184 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 109932 KB Output is correct
2 Correct 67 ms 109932 KB Output is correct
3 Correct 69 ms 109932 KB Output is correct
4 Correct 68 ms 109932 KB Output is correct
5 Correct 69 ms 109932 KB Output is correct
6 Correct 72 ms 109948 KB Output is correct
7 Correct 89 ms 109932 KB Output is correct
8 Correct 72 ms 109932 KB Output is correct
9 Correct 67 ms 109940 KB Output is correct
10 Correct 67 ms 109920 KB Output is correct
11 Correct 71 ms 109932 KB Output is correct
12 Correct 66 ms 110060 KB Output is correct
13 Correct 67 ms 109932 KB Output is correct
14 Correct 67 ms 109932 KB Output is correct
15 Correct 66 ms 109932 KB Output is correct
16 Correct 66 ms 109932 KB Output is correct
17 Correct 65 ms 109932 KB Output is correct
18 Correct 79 ms 109908 KB Output is correct
19 Correct 67 ms 109932 KB Output is correct
20 Correct 71 ms 109932 KB Output is correct
21 Correct 65 ms 110016 KB Output is correct
22 Correct 67 ms 109932 KB Output is correct
23 Correct 72 ms 109932 KB Output is correct
24 Correct 70 ms 109932 KB Output is correct
25 Correct 71 ms 109932 KB Output is correct
26 Correct 69 ms 109932 KB Output is correct
27 Correct 69 ms 109932 KB Output is correct
28 Correct 69 ms 109932 KB Output is correct
29 Correct 70 ms 110060 KB Output is correct
30 Correct 69 ms 109932 KB Output is correct
31 Correct 68 ms 109932 KB Output is correct
32 Correct 70 ms 109932 KB Output is correct
33 Correct 1236 ms 120428 KB Output is correct
34 Correct 1368 ms 131436 KB Output is correct
35 Correct 1328 ms 122604 KB Output is correct
36 Correct 1380 ms 126444 KB Output is correct
37 Correct 1159 ms 121964 KB Output is correct
38 Correct 1154 ms 121776 KB Output is correct
39 Correct 1143 ms 128684 KB Output is correct
40 Correct 1152 ms 128748 KB Output is correct
41 Correct 1117 ms 119916 KB Output is correct
42 Correct 1157 ms 120940 KB Output is correct
43 Correct 1110 ms 119916 KB Output is correct
44 Correct 1137 ms 123756 KB Output is correct
45 Correct 1105 ms 119916 KB Output is correct
46 Correct 1110 ms 120044 KB Output is correct
47 Correct 1117 ms 124268 KB Output is correct
48 Correct 1120 ms 124184 KB Output is correct
49 Correct 1400 ms 123944 KB Output is correct
50 Correct 1375 ms 123756 KB Output is correct
51 Correct 1279 ms 130668 KB Output is correct
52 Correct 1264 ms 130156 KB Output is correct
53 Correct 1353 ms 122220 KB Output is correct
54 Correct 1307 ms 122732 KB Output is correct
55 Correct 1270 ms 120872 KB Output is correct
56 Correct 1307 ms 125608 KB Output is correct
57 Correct 1261 ms 121580 KB Output is correct
58 Correct 1281 ms 122092 KB Output is correct
59 Correct 1145 ms 124268 KB Output is correct