oj.uz

Submission #389189

# Submission time Handle Problem Language Result Execution time Memory
389189 2021-04-13T21:08:17 Z PedroBigMan Horses (IOI15_horses) C++14
100 / 100
 1457 ms 236128 KB 
#include "horses.h"
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

ll fastexp(ll a,ll e) 
{
    if(e==0) {return 1LL;}
    if(e%2LL==0)
    {
        ll v=fastexp(a,(ll) e/2LL); return (v*v)%mod;
    }
    else
    {
        ll v=fastexp(a,(ll) e/2LL); return (((v*v)%mod)*a)%mod;
    }
}

ll inv(ll s) //assumes mod is prime
{
    return fastexp(s,mod-2LL);
}

class ST1
{
    public:
    ll N;
    
    class SV //seg value
    {
        public:
        ld a; ll pos;
        SV() {a=-((ld) INF);}
        SV(ld x) {a=x;}
        SV operator & (SV X) 
		{
			SV ANS(max(a,X.a)); 
			if(a>X.a) {ANS.pos=pos;} else {ANS.pos=X.pos;}
			return ANS;
		}
    };
      
    class LV //lazy value
    {
        public:
        ld a;
        LV() {a=0.0;}
        LV(ld x) {a=x;}
        LV operator & (LV X) {LV ANS(a+X.a); return ANS;}
    };
    
    SV upval(ll c) //how lazy values modify a seg value inside a node, c=current node
    {
        SV X(p[c].a+lazy[c].a); X.pos=p[c].pos;
        return X;
    }
    
    SV neuts; LV neutl;
    
    vector<SV> p;
    vector<LV> lazy;
    vector<pl> range;
    
    ST1() {N=0LL;}
    ST1(vector<ld> arr)
    {
        N = (ll) 1<<(ll) ceil(log2(arr.size()));
        REP(i,0,2*N) {range.pb(mp(0LL,0LL));}
        REP(i,0,N) {p.pb(neuts);}
        REP(i,0,arr.size()) {SV X(arr[i]); p.pb(X); range[i+N]=mp(i,i); p[i+N].pos=i;}
        REP(i,arr.size(),N) {p.pb(neuts); range[i+N]=mp(i,i); p[i+N].pos=i;}
        ll cur = N-1;
        while(cur>0)
        {
            p[cur]=p[2*cur]&p[2*cur+1];
            range[cur]=mp(range[2*cur].ff,range[2*cur+1].ss);
            cur--;
        }
        REP(i,0,2*N) {lazy.pb(neutl);}
    }
    
    void prop(ll c) //how lazy values propagate
    {
        lazy[2*c]=lazy[c]&lazy[2*c]; lazy[2*c+1]=lazy[c]&lazy[2*c+1];
        lazy[c]=neutl;
    }
    
    SV query(ll a,ll b, ll c=1LL) //range [a,b], current node. initially: query(a,b)
    {
        ll x=range[c].ff; ll y=range[c].ss;
        if(y<a || x>b) {return neuts;}
        if(x>=a && y<=b) {return upval(c);}
        prop(c);
		p[c]=upval(c);
        SV ans = query(a,b,2*c)&query(a,b,2*c+1);
        return ans;
    }
    
    void update(LV s, ll a, ll b, ll c=1LL) //update LV, range [a,b], current node, current range. initially: update(s,a,b)
    {
        ll x=range[c].ff; ll y=range[c].ss;
        if(y<a || x>b) {return ;}
        if(x>=a && y<=b) 
        {
            lazy[c]=s&lazy[c]; 
            return;
        }
		prop(c);
        update(s,a,b,2*c); update(s,a,b,2*c+1);
        p[c]=upval(2*c)&upval(2*c+1);
    }
};

class ST2
{
    public:
    ll N;
    
    class SV //seg value
    {
        public:
        ll a; 
        SV() {a=1LL;}
        SV(ll x) {a=x;}
        
        SV operator & (SV X) {SV ANS((a*X.a)%mod); return ANS;}
    };
      
    class LV //lazy value
    {
        public:
        ll a; 
        LV() {a=1LL;}
        LV(ll x) {a=x;}
        
        LV operator & (LV X) {LV ANS((a*X.a)%mod); return ANS;}
    };
    
    SV upval(ll c) //how lazy values modify a seg value inside a node, c=current node
    {
        SV X((p[c].a*fastexp(lazy[c].a,(range[c].ss-range[c].ff+1)))%mod);
        return X;
    }
    
    SV neuts; LV neutl;
    
    vector<SV> p;
    vector<LV> lazy;
    vector<pl> range;
    
    ST2() {N=0LL;}
    ST2(vector<ll> arr)
    {
        N = (ll) 1<<(ll) ceil(log2(arr.size()));
        REP(i,0,2*N) {range.pb(mp(0LL,0LL));}
        REP(i,0,N) {p.pb(neuts);}
        REP(i,0,arr.size()) {SV X(arr[i]); p.pb(X); range[i+N]=mp(i,i);}
        REP(i,arr.size(),N) {p.pb(neuts); range[i+N]=mp(i,i);}
        ll cur = N-1;
        while(cur>0)
        {
            p[cur]=p[2*cur]&p[2*cur+1];
            range[cur]=mp(range[2*cur].ff,range[2*cur+1].ss);
            cur--;
        }
        REP(i,0,2*N) {lazy.pb(neutl);}
    }
    
    void prop(ll c) //how lazy values propagate
    {
        lazy[2*c]=lazy[c]&lazy[2*c]; lazy[2*c+1]=lazy[c]&lazy[2*c+1];
        lazy[c]=neutl;
    }
    
    SV query(ll a,ll b, ll c=1LL) //range [a,b], current node. initially: query(a,b)
    {
        ll x=range[c].ff; ll y=range[c].ss;
        if(y<a || x>b) {return neuts;}
        if(x>=a && y<=b) {return upval(c);}
        prop(c);
		p[c]=upval(c);
        SV ans = query(a,b,2*c)&query(a,b,2*c+1);
        return ans;
    }
    
    void update(LV s, ll a, ll b, ll c=1LL) //update LV, range [a,b], current node, current range. initially: update(s,a,b)
    {
        ll x=range[c].ff; ll y=range[c].ss;
        if(y<a || x>b) {return ;}
        if(x>=a && y<=b) 
        {
            lazy[c]=s&lazy[c]; 
            return;
        }
		prop(c);
        update(s,a,b,2*c); update(s,a,b,2*c+1);
        p[c]=upval(2*c)&upval(2*c+1);
    }
};

ll N;
vector<ld> ps;
vector<ll> X; vector<ll> Y;
ST1 A; ST2 B;

int solve()
{
	ll ind = A.query(0,N-1).pos; 
	ll ans = B.query(0,ind).a;
	ans*=Y[ind]; ans%=mod; if(ans<0LL) {ans+=mod;}
	int x = (int) ans;
	return x;
}

int init(int n, int x[], int y[]) 
{
	N=(ll) n;
	REP(i,0,N) {X.pb((ll) x[i]); Y.pb((ll) y[i]);}
	vector<ld> ps; ld sum=(ld) 0.0; 
	ld val1,val2;
	REP(i,0,N)
	{
		val1 = (ld) log2((ld) X[i]);
		val2 = (ld) log2((ld) Y[i]);
		sum+=val1;
		ps.pb(sum+val2);
	}
	ST1 initA(ps); A=initA;
	ST2 initB(X); B=initB;
	return solve();
}

int updateX(int pos, int v) 
{	
	ll newX = (ll) v; ll oldX = X[pos]; X[pos]=newX;
	ll val1 = (newX*inv(oldX))%mod;
	B.update(val1,pos,pos);
	ld val2 = (ld) log2((ld) newX) - (ld) log2((ld) oldX);
	A.update(val2,pos,N-1);
	return solve();
}

int updateY(int pos, int v) 
{
	ll oldY = Y[pos]; ll newY = (ll) v; Y[pos] = newY;
	ld val = (ld) log2((ld) newY) - (ld) log2((ld) oldY);
	A.update(val,pos,pos);
	return solve();
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:258:13: warning: declaration of 'ps' shadows a global declaration [-Wshadow]
  258 |  vector<ld> ps; ld sum=(ld) 0.0;
      |             ^~
horses.cpp:241:12: note: shadowed declaration is here
  241 | vector<ld> ps;
      |            ^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 292 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 296 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 208 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 296 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 0 ms 304 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 4 ms 716 KB Output is correct
24 Correct 4 ms 704 KB Output is correct
25 Correct 4 ms 720 KB Output is correct
26 Correct 4 ms 704 KB Output is correct
27 Correct 4 ms 776 KB Output is correct
28 Correct 5 ms 776 KB Output is correct
29 Correct 4 ms 716 KB Output is correct
30 Correct 5 ms 716 KB Output is correct
31 Correct 3 ms 716 KB Output is correct
32 Correct 4 ms 696 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 703 ms 227228 KB Output is correct
2 Correct 1200 ms 236076 KB Output is correct
3 Correct 1144 ms 227152 KB Output is correct
4 Correct 1457 ms 231072 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 280 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 308 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 304 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 208 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 4 ms 716 KB Output is correct
24 Correct 4 ms 716 KB Output is correct
25 Correct 4 ms 716 KB Output is correct
26 Correct 4 ms 716 KB Output is correct
27 Correct 4 ms 716 KB Output is correct
28 Correct 5 ms 784 KB Output is correct
29 Correct 4 ms 716 KB Output is correct
30 Correct 5 ms 716 KB Output is correct
31 Correct 3 ms 716 KB Output is correct
32 Correct 4 ms 716 KB Output is correct
33 Correct 351 ms 229020 KB Output is correct
34 Correct 349 ms 229004 KB Output is correct
35 Correct 348 ms 235956 KB Output is correct
36 Correct 349 ms 235956 KB Output is correct
37 Correct 335 ms 227092 KB Output is correct
38 Correct 347 ms 228112 KB Output is correct
39 Correct 331 ms 227076 KB Output is correct
40 Correct 357 ms 230952 KB Output is correct
41 Correct 288 ms 227092 KB Output is correct
42 Correct 311 ms 227148 KB Output is correct
43 Correct 278 ms 231428 KB Output is correct
44 Correct 272 ms 231364 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 4 ms 716 KB Output is correct
24 Correct 4 ms 716 KB Output is correct
25 Correct 4 ms 796 KB Output is correct
26 Correct 4 ms 716 KB Output is correct
27 Correct 4 ms 716 KB Output is correct
28 Correct 5 ms 716 KB Output is correct
29 Correct 4 ms 716 KB Output is correct
30 Correct 5 ms 716 KB Output is correct
31 Correct 3 ms 716 KB Output is correct
32 Correct 4 ms 716 KB Output is correct
33 Correct 683 ms 227184 KB Output is correct
34 Correct 1166 ms 236128 KB Output is correct
35 Correct 1150 ms 227276 KB Output is correct
36 Correct 1418 ms 231064 KB Output is correct
37 Correct 356 ms 229028 KB Output is correct
38 Correct 352 ms 228956 KB Output is correct
39 Correct 340 ms 236060 KB Output is correct
40 Correct 348 ms 235896 KB Output is correct
41 Correct 340 ms 227156 KB Output is correct
42 Correct 345 ms 228052 KB Output is correct
43 Correct 330 ms 227048 KB Output is correct
44 Correct 353 ms 230968 KB Output is correct
45 Correct 288 ms 227032 KB Output is correct
46 Correct 308 ms 227112 KB Output is correct
47 Correct 270 ms 231460 KB Output is correct
48 Correct 273 ms 231472 KB Output is correct
49 Correct 1176 ms 228956 KB Output is correct
50 Correct 1130 ms 229012 KB Output is correct
51 Correct 907 ms 236060 KB Output is correct
52 Correct 947 ms 236052 KB Output is correct
53 Correct 1103 ms 227256 KB Output is correct
54 Correct 1212 ms 228068 KB Output is correct
55 Correct 1079 ms 227220 KB Output is correct
56 Correct 1199 ms 231056 KB Output is correct
57 Correct 634 ms 227260 KB Output is correct
58 Correct 872 ms 227268 KB Output is correct
59 Correct 268 ms 231444 KB Output is correct