제출 #1197904

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197904		haitax511	말 (IOI15_horses)	C++20	0 / 100	344 ms	197160 KiB

horses

// #include<bits/aintocator.h>
// #pragma GCC optimize("Ofast,unroint-loops")
// #ifdef ONLINE_JUDGE
// #pragma GCC target("avx2,fma,bmi,bmi2,popcnt,lzcnt,tune=native")
// #endif
#include"horses.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// VVI
#define fast                      \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);

#define SZ(a) (int)a.size()
#define UNIQUE(a) (a).erase(unique(aint(a)), (a).end())
#define mp make_pair
#define mem(a, b) memset(a, b, sizeof(a))
#define aint(x) x.begin(), x.end()

//Printings & debugging
#define nn '\n'
#define Setpre(n) cout << fixed << setprecision(n)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define debug printf("I am here\n")

// CONSTANTS
#define md 1000007
#define PI acos(-1)
const  long double   EPS = 1e-9;
const int N = 2e5 + 10;
const int M = 1e9 + 7;

/// INLINE FUNCTIONS
inline int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }
inline int LCM(int a, int b) { return a * b / GCD(a, b); }
inline  long double   logb(int base, int num) { return ( long double  )log(num) / ( long double  )log(base); }


const int INF=1e15+500;
// int mul(int x) {return x==0 ? 1 : mul(x-1)*10;}
const int MAXN=3e5+100;
const int MOD=1e9+7;
#define p(i,n) for(int i=0; i<n; i++)
#define rp(i,n) for(int i=n-1; i>=0; i--)
#define grid_int vector<vector<int>>
#define grid_char vector<vector<char>>
void ADD(int& c,int a, int b, int m) {c = ((a % m) + (b % m)) % m;return;}
void MUL(int& c,int a, int b, int m) {c = ((a % m) * (b % m)) % m;}
void SUB(int& c,int a, int b, int m) {c = ((a % m) - (b % m) + m) % m;}
void MIN(int& a, int b) {a = min(a, b);}
void MAX(int& a, int b) {a = max(a, b);}
int gcdExtended(int a, int b, int *x, int *y);
int modInverse(int b, int m){int x,y;int g = gcdExtended(b, m, &x, &y);if (g != 1)return -1;return (x%m + m) % m;}
int modDivide(int a, int b, int m){a = a % m;int inv = modInverse(b, m);return (inv * a) % m;}
int gcdExtended(int a, int b, int *x, int *y){if (a == 0){*x = 0, *y = 1;return b;}int x1, y1;int gcd = gcdExtended(b%a, a, &x1, &y1);*x = y1 - (b/a) * x1;*y = x1;return gcd;}
#define f first
#define s second
#define ll long long
#define pb push_back//SEGGY FOR max pref sum;
vector<int> xi, yi;
int nnn;
struct item {
    double lg;
    int idx;
    int val;
    // VAL IS THE XI
    // LG IS LOG OF SELLING AT DAY index
    // iDX IS INDEX
};


struct segtree {
    vector<item> seggy;
    vector<double> lazy;
    int n;

    segtree(int _n) {
        n = _n;
        seggy.resize(4 * n);
        lazy.resize(4 * n, 0);
    }

    item merge(item a, item b) {
        item x;
        if (a.lg > b.lg) {
            x.lg = a.lg;
            x.idx = a.idx;
        } else {
            x.lg = b.lg;
            x.idx = b.idx;
        }
        MUL(x.val, a.val, b.val, MOD);
        return x;
    }

    void push(int node, int left, int right) {
        if (lazy[node] != 0) {
            seggy[node].lg += lazy[node];
            if (left != right) {
                lazy[2 * node] += lazy[node];
                lazy[2 * node + 1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }

    void build(int node, int left, int right) {
        if (left == right) {
            seggy[node].idx = left;
            seggy[node].lg = log(yi[left]);
            seggy[node].val = xi[left];
        } else {
            int mid = (left + right) / 2;
            build(2 * node, left, mid);
            build(2 * node + 1, mid + 1, right);
            seggy[node] = merge(seggy[2 * node], seggy[2 * node + 1]);
        }
    }

    // Point update to set new value and log
    void update(int node, int left, int right, int idx, int vv) {
        push(node, left, right);
        if (left == right) {
            seggy[node].idx = left;
            seggy[node].lg = log(vv);
            seggy[node].val = vv;
        } else {
            int mid = (left + right) / 2;
            if (idx > mid) update(2 * node + 1, mid + 1, right, idx, vv);
            else update(2 * node, left, mid, idx, vv);
            seggy[node] = merge(seggy[2 * node], seggy[2 * node + 1]);
        }
    }

    // Point update to add value to lg
    void update_lg(int node, int left, int right, int idx, double vv) {
        if (left == right) {
            seggy[node].idx = left;
            seggy[node].lg += vv;
            return;
        }
        int mid = (left + right) / 2;
        if (idx > mid) update_lg(2 * node + 1, mid + 1, right, idx, vv);
        else update_lg(2 * node, left, mid, idx, vv);
        seggy[node] = merge(seggy[2 * node], seggy[2 * node + 1]);
    }

    // New range update function for .lg using lazy propagation
    void lazyx(int node, int left, int right, int l, int r, double add_val) {
        push(node, left, right);
        if (r < left || l > right) return;

        if (l <= left && right <= r) {
            lazy[node] += add_val;
            push(node, left, right);
            return;
        }

        int mid = (left + right) / 2;
        lazyx(2 * node, left, mid, l, r, add_val);
        lazyx(2 * node + 1, mid + 1, right, l, r, add_val);
        seggy[node] = merge(seggy[2 * node], seggy[2 * node + 1]);
    }

    int query(int node, int left, int right, int l, int r) {
        push(node, left, right);
        if (l > right || r < left) return 1;
        if (left >= l && right <= r) return seggy[node].val % MOD;

        int mid = (left + right) / 2;
        int xx = query(2 * node, left, mid, l, r);
        int yy = query(2 * node + 1, mid + 1, right, l, r);
        int temp;
        MUL(temp, xx, yy, MOD);
        return temp;
    }

    item grab() {
        return seggy[1]; // root is usually at index 1
    }
};

segtree Tree(2e6+200);
int opt(vector<int>& a, vector<int>& b, int n) {
    item x = Tree.grab();
    int ppp = Tree.query(1, 0, nnn - 1, 0, x.idx);
    int temp;
    MUL(temp, ppp, yi[x.idx], MOD);
    return temp;
}

// the functions that are asked by the grader
int init(int n, int X[], int Y[]) {
    nnn = n;
    xi.resize(nnn);
    yi.resize(nnn);
    for (int i = 0; i < n; i++) {
        xi[i] = X[i];
        Tree.lazyx(1,0,n-1,i,n-1,log(xi[i]));
    }
    for (int i = 0; i < n; i++) yi[i] = Y[i];
	Tree.build(1,0,n-1);

    return opt(xi, yi, n);
}

int updateX(int pos, int val) {
    Tree.update_lg(1, 0, nnn - 1, pos, log(val) - log(xi[pos]));
    xi[pos] = val;

    Tree.update(1, 0, nnn - 1, pos, val);

    return opt(xi, yi, nnn);
}

int updateY(int pos, int val) {
    Tree.update_lg(1, 0, nnn - 1, pos, log(val) - log(yi[pos]));
    yi[pos] = val;

    return opt(xi, yi, nnn);
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp:45:19: warning: overflow in conversion from 'double' to 'int' changes value from '1.0000000000005e+15' to '2147483647' [-Woverflow]
   45 | const int INF=1e15+500;
      |               ~~~~^~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23