oj.uz

Submission #533221

# Submission time Handle Problem Language Result Execution time Memory
533221 2022-03-05T06:56:04 Z ivan24 Horses (IOI15_horses) C++14
100 / 100
 981 ms 88200 KB 
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;

using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second

ll min (ll x, ll y){
    return ((x < y) ? x : y);
}

ll max (ll x, ll y){
    return ((x > y) ? x : y);
}

const ll INF = 1e18+10;
const ll MOD = 1e9+7;
const ll MX_VAL = 1e9;

struct stnode {
    ll prod,mx;
    stnode (){ prod = 1; mx = 0; }
    stnode merge_node (const stnode& rhs){
        stnode res;
        res.prod = prod*rhs.prod; res.prod %= MOD;
        res.mx = max(mx,rhs.mx);
        return res;
    }
};

ll modpow (ll b, ll e){
    ll res = 1;
    while (e > 0){
        if (e%2) res *= b;
        e /= 2; b *= b;
        res %= MOD; b %= MOD;
    }
    return res;
}

struct frac {
    ll n,d;
    frac(){ n = 1; d = 1;}
    frac (ll _n, ll _d){
        n = _n; d = _d;
    }
    bool operator>(const frac& rhs) const{
        return n*rhs.d > rhs.n*d;
    }
    bool operator<(const frac& rhs) const{
        return n*rhs.d < rhs.n*d;
    }
    ll mult (ll x){
        x *= n; x %= MOD;
        x *= modpow(d,MOD-2); x %= MOD;
        return x;
    }
};

class SegTree {
private:
    vector<stnode> st;
    ll n;
    vi a,b;
    ll left(ll x){ return (x << 1); }
    ll right(ll x){ return ((x << 1) + 1); }
    void build (ll i, ll l, ll r){
        if (l == r){
            st[i].prod = a[i];
            st[i].mx = b[i];
        }else{
            ll m = (l+r)/2;
            build(left(i),l,m);
            build(right(i),m+1,r);
            st[i] = st[left(i)].merge_node(st[right(i)]);
        }
    }
    stnode query (ll i, ll l, ll r, ll ql, ll qr){
        if (qr >= r && l >= ql){
            return st[i];
        }else if (l > qr || ql > r){
            return stnode();
        }else{
            ll m = (l+r)/2;
            stnode lres = query(left(i),l,m,ql,qr);
            stnode rres = query(right(i),m+1,r,ql,qr);
            return lres.merge_node(rres);
        }
    }
    void update (ll i, ll l, ll r, ll type, ll val, ll idx){
        //cout << i << " " << l << " " << r << " " << type << " " << val << " " << idx << endl;
        if (r >= idx && idx >= l){
            //cout << i << " " << l << " " << r << " " << type << " " << val << " " << idx << endl;
            if (r == l){
                if (type == 0) st[i].prod = val;
                else st[i].mx = val;
            }else{
                ll m = (l+r)/2;
                update(left(i),l,m,type,val,idx);
                update(right(i),m+1,r,type,val,idx);
                st[i] = st[left(i)].merge_node(st[right(i)]);
            }
        }
    }
public:
    SegTree (vi _a, vi _b): a(_a), b(_b){
        n = a.size();
        st.resize(4*n);
        build(1,0,n-1);
    }
    SegTree(ll _n){
        n = _n;
        a.assign(n,1);
        b.assign(n,0);
        st.assign(4*n,stnode());
    }
    SegTree(){}
    ll query (ll type, ll l, ll r){
        stnode res;
        //cout << "queried: " << type << " " << l << " " << r << endl;
        if (r >= l) res = query(1,0,n-1,l,r);
        if (type == 0) return res.prod;
        else return res.mx;
    }
    void update (ll type, ll val, ll idx){
        //cout << "update: " << type << " " << val << " " << idx << endl;
        //cout << n << endl;
        update (1,0,n-1,type,val,idx);
    }
};

class WeirdDS {
private:
    SegTree st;
    vi x,y;
    set<ll> overone;
    ll n;
public:
    WeirdDS(int _n){
        n = _n;
        st = SegTree(n);
        x.assign(n,1);
        y.assign(n,0);
        set<ll>().swap(overone);
        overone.insert(0);
    }
    WeirdDS(){}
    void updateX(ll pos, ll val){
        st.update(0,val,pos);
        if (val == 1){
            auto itr = overone.find(-pos);
            if (itr != overone.end())
                overone.erase(itr);
        }else{
            overone.insert(-pos);
        }
        overone.insert(0);
        x[pos] = val;
    }
    void updateY(ll pos, ll val){
        st.update(1,val,pos);
    }
    ll query (){
        bool broke = false;
        ll prv = n;
        ll ctr = 1;
        frac maxMult;
        for (auto i: overone){
            ll bigY = st.query(1,-i,prv-1);
            frac curMult = frac(bigY,ctr);
            if (curMult > maxMult) maxMult = curMult;
            prv = -i;
            ctr *= x[-i];
            if (x[-i] == 1 && i != 0) return INF;
            if (ctr > MX_VAL) break;
        }
        return maxMult.mult(st.query(0,0,n-1));
    }
};

WeirdDS myDS;

int init(int n, int x[], int y[]) {
    //cout.setstate(ios_base::failbit);
    myDS = WeirdDS(n);
    for (ll i = 0; n > i; i++){
        myDS.updateX(i,x[i]);
        myDS.updateY(i,y[i]);
    }
    ////cout << myDS.query() << endl;
	return myDS.query();
}

int updateX(int pos, int val) {
    //cout << "updateX: " << pos << " " << val << endl;
    myDS.updateX(pos,val);
    //cout << res << endl;
	return myDS.query();
}

int updateY(int pos, int val) {
    //cout << "updateY: " << pos << " " << val << endl;
    myDS.updateY(pos,val);
    //cout << res << endl;
	return myDS.query();
}

Compilation message

horses.cpp: In member function 'll WeirdDS::query()':
horses.cpp:170:14: warning: unused variable 'broke' [-Wunused-variable]
  170 |         bool broke = false;
      |              ^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:197:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  197 |  return myDS.query();
      |         ~~~~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:204:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  204 |  return myDS.query();
      |         ~~~~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:211:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  211 |  return myDS.query();
      |         ~~~~~~~~~~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 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 1 ms 308 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 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 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 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 0 ms 204 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 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 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 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 0 ms 204 KB Output is correct
16 Correct 0 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 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 4 ms 332 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 3 ms 332 KB Output is correct
32 Correct 3 ms 332 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 951 ms 77416 KB Output is correct
2 Correct 611 ms 88200 KB Output is correct
3 Correct 602 ms 79320 KB Output is correct
4 Correct 665 ms 83268 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 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 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 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 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 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 2 ms 332 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 4 ms 332 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 3 ms 332 KB Output is correct
32 Correct 3 ms 332 KB Output is correct
33 Correct 267 ms 51308 KB Output is correct
34 Correct 262 ms 51304 KB Output is correct
35 Correct 485 ms 74684 KB Output is correct
36 Correct 441 ms 74688 KB Output is correct
37 Correct 299 ms 51308 KB Output is correct
38 Correct 369 ms 63296 KB Output is correct
39 Correct 267 ms 53148 KB Output is correct
40 Correct 436 ms 80700 KB Output is correct
41 Correct 290 ms 53224 KB Output is correct
42 Correct 292 ms 53276 KB Output is correct
43 Correct 430 ms 81016 KB Output is correct
44 Correct 431 ms 81032 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 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 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 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 0 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 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 0 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 2 ms 332 KB Output is correct
24 Correct 3 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 6 ms 332 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 3 ms 332 KB Output is correct
32 Correct 4 ms 332 KB Output is correct
33 Correct 981 ms 77552 KB Output is correct
34 Correct 617 ms 88168 KB Output is correct
35 Correct 636 ms 79436 KB Output is correct
36 Correct 685 ms 83400 KB Output is correct
37 Correct 255 ms 55244 KB Output is correct
38 Correct 254 ms 55236 KB Output is correct
39 Correct 420 ms 85548 KB Output is correct
40 Correct 447 ms 85532 KB Output is correct
41 Correct 319 ms 53448 KB Output is correct
42 Correct 369 ms 66324 KB Output is correct
43 Correct 244 ms 53240 KB Output is correct
44 Correct 424 ms 80592 KB Output is correct
45 Correct 273 ms 53368 KB Output is correct
46 Correct 281 ms 53324 KB Output is correct
47 Correct 390 ms 81196 KB Output is correct
48 Correct 401 ms 80928 KB Output is correct
49 Correct 385 ms 58288 KB Output is correct
50 Correct 374 ms 58212 KB Output is correct
51 Correct 588 ms 87528 KB Output is correct
52 Correct 523 ms 87028 KB Output is correct
53 Correct 905 ms 56548 KB Output is correct
54 Correct 561 ms 70080 KB Output is correct
55 Correct 347 ms 54216 KB Output is correct
56 Correct 508 ms 82396 KB Output is correct
57 Correct 663 ms 54956 KB Output is correct
58 Correct 785 ms 55372 KB Output is correct
59 Correct 444 ms 80932 KB Output is correct