답안 #1065519

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1065519 2024-08-19T08:53:23 Z anango 말 (IOI15_horses) C++17
0 / 100
332 ms 56804 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;

int 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) {
            bestsuffprod = suffprod;
            bestyval = maxyval;
            answer = maxyval*xseg.query_wrapper(needcheck[i]); 
            answer%=MOD;
        }

        suffprod*=needcheck[xval[i]];
    }
    return 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();
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:160:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  160 |  return get_answer();
      |         ~~~~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:166:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  166 |  return get_answer();
      |         ~~~~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:172:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  172 |  return get_answer();
      |         ~~~~~~~~~~^~
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Incorrect 5 ms 16732 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Incorrect 3 ms 16732 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 332 ms 56804 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16732 KB Output is correct
2 Incorrect 3 ms 16732 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 16732 KB Output is correct
2 Incorrect 3 ms 16728 KB Output isn't correct
3 Halted 0 ms 0 KB -