oj.uz

답안 #1065528

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1065528 2024-08-19T08:58:54 Z anango 말 (IOI15_horses) C++17
37 / 100
 540 ms 65620 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;
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 3 ms 16792 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16808 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 3 ms 16760 KB Output is correct
9 Correct 3 ms 16876 KB Output is correct
10 Correct 5 ms 16728 KB Output is correct
11 Correct 3 ms 16728 KB Output is correct
12 Correct 3 ms 16732 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Correct 4 ms 16732 KB Output is correct
15 Correct 4 ms 16732 KB Output is correct
16 Correct 3 ms 16728 KB Output is correct
17 Correct 3 ms 16728 KB Output is correct
18 Correct 4 ms 16732 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 3 ms 16724 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 4 ms 16732 KB Output is correct
9 Correct 3 ms 16732 KB Output is correct
10 Correct 4 ms 16728 KB Output is correct
11 Correct 3 ms 16732 KB Output is correct
12 Correct 3 ms 16872 KB Output is correct
13 Correct 4 ms 16932 KB Output is correct
14 Correct 3 ms 16732 KB Output is correct
15 Correct 4 ms 16732 KB Output is correct
16 Correct 5 ms 16732 KB Output is correct
17 Correct 3 ms 16732 KB Output is correct
18 Correct 4 ms 16732 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 3 ms 16732 KB Output is correct
21 Incorrect 3 ms 16732 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 540 ms 53104 KB Output is correct
2 Correct 392 ms 65620 KB Output is correct
3 Correct 408 ms 56656 KB Output is correct
4 Correct 406 ms 60500 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 3 ms 16732 KB Output is correct
9 Correct 4 ms 16984 KB Output is correct
10 Correct 4 ms 16732 KB Output is correct
11 Correct 3 ms 16732 KB Output is correct
12 Correct 4 ms 16872 KB Output is correct
13 Correct 3 ms 16728 KB Output is correct
14 Correct 4 ms 16732 KB Output is correct
15 Correct 3 ms 16732 KB Output is correct
16 Correct 3 ms 16732 KB Output is correct
17 Correct 3 ms 16732 KB Output is correct
18 Correct 4 ms 16728 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 4 ms 16876 KB Output is correct
21 Incorrect 3 ms 16880 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 4 ms 16728 KB Output is correct
3 Correct 4 ms 16860 KB Output is correct
4 Correct 3 ms 16728 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16872 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 3 ms 16876 KB Output is correct
9 Correct 4 ms 16732 KB Output is correct
10 Correct 4 ms 16628 KB Output is correct
11 Correct 4 ms 16732 KB Output is correct
12 Correct 3 ms 16732 KB Output is correct
13 Correct 4 ms 16732 KB Output is correct
14 Correct 4 ms 16732 KB Output is correct
15 Correct 3 ms 16732 KB Output is correct
16 Correct 4 ms 16732 KB Output is correct
17 Correct 3 ms 16732 KB Output is correct
18 Correct 3 ms 16728 KB Output is correct
19 Correct 4 ms 16876 KB Output is correct
20 Correct 3 ms 16732 KB Output is correct
21 Incorrect 4 ms 16732 KB Output isn't correct
22 Halted 0 ms 0 KB -