oj.uz

Submission #1065540

# Submission time Handle Problem Language Result Execution time Memory
1065540 2024-08-19T09:04:28 Z anango Horses (IOI15_horses) C++17
17 / 100
 35 ms 41840 KB 
#include "horses.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;

int MOD = 1000000007;
int INF = 1LL<<60;

//maintain a set of all indices such that X[i]>1
//consider the last 30 such indices
//then using a max segtree calculate the maximum Y[i] in between these indices, and thus compute the max X[i]*Y[i] at that index
//we can compute the prefix products of the X[i] using another segtree, which allows us to make point updates
//and range product queries

int exp(int base, int exponent) {
    int t = base;
    int p = 1;
    for (int i=0; i<32; i++) {
        if (exponent&(1LL<<i)) {
            p*=t; p%=MOD;
        }
        t*=t;
        t%=MOD;
    }
    return p;
}

int inv(int base) {
    return exp(base,MOD-2);
}

class productSegTree {
public:
    const int sz = 1048576;
    vector<int> tree;
    productSegTree() {
        tree=vector<int>(sz,1);
    }
    //each node carries the product of its children
    void update(int v, int l, int r, int tl, int tr, int assignment) {
        if (l>tr || r<tl) return;
        if (l<=tl && tr<=r) {
            tree[v]=assignment;
            tree[v]%=MOD;
            return;
        }
        int m = (tl+tr)/2;
        update(2*v,l,r,tl,m,assignment);
        update(2*v+1,l,r,m+1,tr,assignment);
        tree[v] = tree[2*v]*tree[2*v+1];
        tree[v]%=MOD;
    }
    int query(int v, int l, int r, int tl, int tr) {
        if (l>tr || r<tl) return 1;
        if (l<=tl && tr<=r) {
            return tree[v];
        }
        int m = (tl+tr)/2;
        int a = query(2*v,l,r,tl,m);
        int b = query(2*v+1,l,r,m+1,tr);
        return (a*b)%MOD;
    }

    void update_wrapper(int index, int mult) {
        update(1,index,index,0,sz/2-1,mult);
    }
    int query_wrapper(int index) {
        //0...index
        return query(1,0,index,0,sz/2-1);
    }
};

class maxSegTree {
public:
    const int sz = 1048576;
    vector<int> tree;
    maxSegTree() {
        tree=vector<int>(sz,0);
    }
    //each node carries the max of its children
    void update(int v, int l, int r, int tl, int tr, int assignment) {
        if (l>tr || r<tl) return;
        if (l<=tl && tr<=r) {
            tree[v]=assignment;
            return;
        }
        int m = (tl+tr)/2;
        update(2*v,l,r,tl,m,assignment);
        update(2*v+1,l,r,m+1,tr,assignment);
        tree[v] = max(tree[2*v],tree[2*v+1]);
    }
    int query(int v, int l, int r, int tl, int tr) {
        if (l>tr || r<tl) return -INF;
        if (l<=tl && tr<=r) {
            return tree[v];
        }
        int m = (tl+tr)/2;
        int a = query(2*v,l,r,tl,m);
        int b = query(2*v+1,l,r,m+1,tr);
        return max(a,b);
    }
    void update_wrapper(int index, int assignment) {
        update(1,index,index,0,sz/2-1,assignment);
    }
    int query_wrapper(int l, int r) {
        return query(1,l,r,0,sz/2-1);
    }
};

set<int> usefulX;
vector<int> xval,yval;
maxSegTree yseg;
productSegTree xseg;
int n;

signed get_answer() {
    vector<int> needcheck={0};
    auto it = usefulX.end();
    for (int i=0; i<32; i++) {
        if (it==usefulX.begin()) break;
        it--;
        int r = *it;
        needcheck.push_back(r);
    }
    needcheck.push_back(n);
    sort(needcheck.begin(), needcheck.end());
    int answer = -1;
    int suffprod = 1;
    int bestyval = 0;
    int bestsuffprod = 1;
    //want maximum value of maxyval / suffprod
    int k = needcheck.size();
    for (int i=k-2; i>=0; i--) {
        if (suffprod>1073741824) break;
        int maxyval = yseg.query_wrapper(needcheck[i],needcheck[i+1]-1);
        if (maxyval*bestsuffprod>bestyval*suffprod) {
            //cout << "changed " << i << " " << maxyval <<" " << bestsuffprod <<" " << bestyval <<" " << suffprod << endl;
            bestsuffprod = suffprod;
            bestyval = maxyval;
            answer = maxyval*xseg.query_wrapper(needcheck[i]); 
            answer%=MOD;
        }
        //cout << "trying " << i <<" " << needcheck[i] <<" " << needcheck[i+1] <<" " << maxyval <<" " << suffprod << " " << maxyval*xseg.query_wrapper(needcheck[i]) << endl;

        suffprod*=xval[needcheck[i]];
    }
    return (signed)answer;

}

signed init(signed N, signed X[], signed Y[]) {
    n=N;
    assert(n<11);
    xval=yval=vector<int>(N,0);
    for (int i=0; i<N; i++) {
        xval[i] = X[i]; yval[i] = Y[i];
        if (xval[i]!=1) usefulX.insert(i);
    }
    for (int i=0; i<N; i++) {
        xseg.update_wrapper(i,X[i]);
        yseg.update_wrapper(i,Y[i]);
    }
	return get_answer();
}

signed updateX(signed pos, signed val) {
    xval[pos] = val;	
    xseg.update_wrapper(pos,val);
	return get_answer();
}

signed updateY(signed pos, signed val) {
    yval[pos] = val;
    yseg.update_wrapper(pos,val);
	return get_answer();
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16732 KB Output is correct
2 Correct 7 ms 16808 KB Output is correct
3 Correct 6 ms 16732 KB Output is correct
4 Correct 7 ms 16728 KB Output is correct
5 Correct 7 ms 16816 KB Output is correct
6 Correct 9 ms 16732 KB Output is correct
7 Correct 7 ms 16732 KB Output is correct
8 Correct 6 ms 16860 KB Output is correct
9 Correct 7 ms 16728 KB Output is correct
10 Correct 7 ms 16728 KB Output is correct
11 Correct 6 ms 16732 KB Output is correct
12 Correct 6 ms 16732 KB Output is correct
13 Correct 7 ms 16732 KB Output is correct
14 Correct 7 ms 16636 KB Output is correct
15 Correct 6 ms 16732 KB Output is correct
16 Correct 7 ms 16868 KB Output is correct
17 Correct 7 ms 16708 KB Output is correct
18 Correct 6 ms 16728 KB Output is correct
19 Correct 6 ms 16732 KB Output is correct
20 Correct 6 ms 16732 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16828 KB Output is correct
2 Correct 7 ms 16660 KB Output is correct
3 Correct 6 ms 16656 KB Output is correct
4 Correct 6 ms 16732 KB Output is correct
5 Correct 7 ms 16732 KB Output is correct
6 Correct 6 ms 16828 KB Output is correct
7 Correct 9 ms 16732 KB Output is correct
8 Correct 7 ms 16732 KB Output is correct
9 Correct 7 ms 16732 KB Output is correct
10 Correct 7 ms 16732 KB Output is correct
11 Correct 6 ms 16732 KB Output is correct
12 Correct 6 ms 16732 KB Output is correct
13 Correct 7 ms 16732 KB Output is correct
14 Correct 6 ms 16732 KB Output is correct
15 Correct 6 ms 16732 KB Output is correct
16 Correct 6 ms 16772 KB Output is correct
17 Correct 6 ms 16732 KB Output is correct
18 Correct 7 ms 16728 KB Output is correct
19 Correct 7 ms 16732 KB Output is correct
20 Correct 6 ms 16732 KB Output is correct
21 Incorrect 6 ms 16732 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 41840 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16728 KB Output is correct
2 Correct 6 ms 16732 KB Output is correct
3 Correct 6 ms 16772 KB Output is correct
4 Correct 7 ms 16676 KB Output is correct
5 Correct 6 ms 16732 KB Output is correct
6 Correct 6 ms 16776 KB Output is correct
7 Correct 6 ms 16728 KB Output is correct
8 Correct 6 ms 16732 KB Output is correct
9 Correct 7 ms 16984 KB Output is correct
10 Correct 6 ms 16732 KB Output is correct
11 Correct 7 ms 16732 KB Output is correct
12 Correct 8 ms 16704 KB Output is correct
13 Correct 7 ms 16732 KB Output is correct
14 Correct 6 ms 16732 KB Output is correct
15 Correct 6 ms 16732 KB Output is correct
16 Correct 7 ms 16732 KB Output is correct
17 Correct 6 ms 16844 KB Output is correct
18 Correct 7 ms 16732 KB Output is correct
19 Correct 6 ms 16732 KB Output is correct
20 Correct 7 ms 16732 KB Output is correct
21 Incorrect 6 ms 16732 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16732 KB Output is correct
2 Correct 7 ms 16732 KB Output is correct
3 Correct 6 ms 16732 KB Output is correct
4 Correct 7 ms 16696 KB Output is correct
5 Correct 7 ms 16728 KB Output is correct
6 Correct 7 ms 16732 KB Output is correct
7 Correct 7 ms 16728 KB Output is correct
8 Correct 7 ms 16732 KB Output is correct
9 Correct 7 ms 16732 KB Output is correct
10 Correct 9 ms 16668 KB Output is correct
11 Correct 7 ms 16864 KB Output is correct
12 Correct 7 ms 16728 KB Output is correct
13 Correct 7 ms 16728 KB Output is correct
14 Correct 7 ms 16732 KB Output is correct
15 Correct 6 ms 16676 KB Output is correct
16 Correct 7 ms 16732 KB Output is correct
17 Correct 7 ms 16732 KB Output is correct
18 Correct 7 ms 16704 KB Output is correct
19 Correct 6 ms 16732 KB Output is correct
20 Correct 6 ms 16732 KB Output is correct
21 Incorrect 7 ms 16732 KB Output isn't correct
22 Halted 0 ms 0 KB -