Submission #396435

#	Time	Username	Problem	Language	Result	Execution time	Memory
396435		ly20	말 (IOI15_horses)	C++17	17 / 100	795 ms	44704 KiB

horses

//#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 512345, MOD = 1e9 + 7;
pair <int, int> seg[4*MAXN];
int mult[4 * MAXN];
int x[MAXN], y[MAXN];
set <int> s;
set <int> :: iterator it;
int n;
void build(int cur, int ini, int fim) {
    if(ini == fim) {
        seg[cur] = make_pair(y[ini], ini);
        return;
    }
    int m = (ini + fim) / 2;
    int e = 2 * cur, d = 2 * cur + 1;
    build(e, ini, m); build(d, m + 1, fim);
    seg[cur] = max(seg[e], seg[d]);
}
void buildm(int cur, int ini, int fim) {
    if(ini == fim) {
        mult[cur] = x[ini];
        return;
    }
    int m = (ini + fim) / 2;
    int e = 2 * cur, d = 2* cur + 1;
    buildm(e, ini, m); build(d, m + 1, fim);
    mult[cur] = ((long long) mult[e] * mult[d]) % MOD;
}
void updatem(int cur, int ini, int fim, int id, int val) {
    if(ini > id || fim < id) return;
    if(ini == fim) {
        mult[cur] = val;
        return;
    }
    int m = (ini + fim) / 2;
    int e = 2 * cur, d = 2 * cur + 1;
    updatem(e, ini, m, id, val); updatem(d, m + 1, fim, id, val);
    mult[cur] = ((long long) mult[e] * mult[d]) % MOD;
}
int querym(int cur, int ini, int fim, int a, int b) {
    if(ini > b || fim < a) return 1;
    if(ini >= a && fim <= b) return mult[cur];
    int m = (ini + fim) / 2;
    int e = 2 * cur, d = 2 * cur + 1;
    return ( (long long) querym(e, ini, m, a, b) * querym(d, m + 1, fim, a, b)) % MOD;
}
void update(int cur, int ini, int fim, int id, int val) {
    if(ini > id || fim < id) return;
    if(ini == fim) {
        seg[cur].second = val;
        return;
    }
    int m = (ini + fim) / 2;
    int e = 2 * cur, d=  2 * cur + 1;
    update(e, ini, m, id, val); update(d, m + 1, fim, id, val);
    seg[cur] = max(seg[e], seg[d]);
}
pair <int, int> query(int cur, int ini, int fim, int a, int b) {
    if(ini > b || fim < a) return make_pair(0, 0);
    if(ini >= a && fim <= b) return seg[cur];
    int m = (ini + fim) / 2;
    int e = 2 * cur, d=  2* cur + 1;
    return max(query(e, ini, m, a, b), query(d, m + 1, fim, a, b));
}
int acha() {
    vector <int> v;
    v.push_back(n);
    long long at = 1;
    if(s.size() == 0) {
        return query(1, 0, n- 1, 0, n - 1).first;
    }
    it = s.end();
    while(it != s.begin() && at < MOD) {
        it--;
        at = at * x[(*it)];
        if(at < MOD) v.push_back(*it);
    }
    at = 1;
    long long mx = 1;
    int id = -1;
    for(int i = v.size() - 1; i > 0; i--) {
        at *= x[v[i]];
        int a  = v[i], b = v[i - 1] - 1;
        pair <int, int> ya = query(1, 0, n - 1, a, b);
        if(at * ya.first > mx) {
            mx = at * ya.first;
            id = ya.second;
        }
    }
    return mx % MOD;
}
int init(int N, int X[], int Y[]) {
    n = N;
    for(int i = 0; i < n; i++) {
        x[i] = X[i]; y[i] = Y[i];
        if(x[i] > 1) s.insert(i);
    }
    build(1, 0, n - 1); buildm(1, 0, n - 1);
	return acha();
}

int updateX(int pos, int val) {
    if(x[pos] == 1 && val != 1) {
        s.insert(pos);
        updatem(1, 0, n - 1, pos, val);
    }
    else if(x[pos] != 1 && val == 1) {
        s.erase(pos);
        updatem(1, 0, n -1, pos, val);
    }
	return acha();
}

int updateY(int pos, int val) {
    y[pos] = val;
    update(1, 0, n - 1, pos, val);
	return acha();
}

Compilation message (stderr)

horses.cpp: In function 'void buildm(int, int, int)':
horses.cpp:29:49: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   29 |     mult[cur] = ((long long) mult[e] * mult[d]) % MOD;
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void updatem(int, int, int, int, int)':
horses.cpp:40:49: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   40 |     mult[cur] = ((long long) mult[e] * mult[d]) % MOD;
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int querym(int, int, int, int, int)':
horses.cpp:47:81: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   47 |     return ( (long long) querym(e, ini, m, a, b) * querym(d, m + 1, fim, a, b)) % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int acha()':
horses.cpp:83:26: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   83 |     for(int i = v.size() - 1; i > 0; i--) {
      |                 ~~~~~~~~~^~~
horses.cpp:92:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   92 |     return mx % MOD;
      |            ~~~^~~~~
horses.cpp:82:9: warning: variable 'id' set but not used [-Wunused-but-set-variable]
   82 |     int id = -1;
      |         ^~

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