Submission #996819

#	Time	Username	Problem	Language	Result	Execution time	Memory
996819		hasan2006	Horses (IOI15_horses)	C++17	0 / 100	856 ms	50452 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 5e5 + 9 , mod = 1e9 +7;
ll a[N] , b[N] , d[N] , c[N] , dp[N] , t[4 * N];


void pushup(int i){
    t[i] = max(t[2 * i] , t[2 * i + 1]);
}


void add(int i , int l , int r , int tl , int tr , int x){
    int m = (l + r) / 2;
    if(l > tr || r < tl) return;
    if(l >= tl && r <= tr){
        t[i] = x;
    }else {
        add(2 * i , l , m , tl , tr , x);
        add(2 * i + 1 , m + 1 , r , tl , tr , x);
        pushup(i);
    }
}

ll get(int i , int l , int r , int tl , int tr){
    int m = (l + r) / 2;
    if(l > tr || r < tl) return 0;
    if(l >= tl && r <= tr){
        return t[i];
   } else
        return max(get(2 * i , l , m , tl , tr) , get(2 * i + 1 , m + 1 , r , tl , tr));
}



ll f = 1 , n;
set<int>st;
ll binpow(ll x , ll n){
    ll ans = 1;
    while(n > 0){
        if(n % 2) ans = (ans * x) % mod , n--;
        else x = (x * x) % mod , n /= 2;
    }
    return ans;
}

ll divmod(ll a , ll b){
    return (a * binpow(b % mod , mod - 2)) % mod;
}
ll mul(ll a , ll b){
    return (a * b) % mod;
}


int getans(){
    ll  l , r = n - 1, x= 1 , k = f;
    if(st.find(0) == st.end())
        st.insert(0);
    auto it = st.end();
    it--;
    cout<<x<<" "<<k<<"\n";
    while(1){
        l = get(1 , 1 , n , *it + 1 , r + 1 );
        x = max(x , l);
        k = divmod(k , a[*it]);
        x *= a[*it];
        if(x > mod)
            return ((x % mod) * k) % mod;
        if(it == st.begin())
            break;
        r = *it - 1;
        it--;
    }
    return (x % mod) * k % mod;
}

int init(int N, int X[], int Y[]) {
    n = N;
    for(int i = 0; i < n; i++){
        a[i] = X[i] , b[i] = Y[i];
        f = (f * a[i]) % mod;
        if(a[i] > 1)
            st.insert(i);
        add(1 , 1 , n , i + 1 , i + 1 , b[i]);
    }
	return getans();
}



int updateX(int pos, int val) {
	f = divmod(f , a[pos]);
	if(a[pos] > 1)
        st.erase(pos);
	a[pos] = val;
	f = mul(f , a[pos]);
	if(a[pos] > 1)
        st.insert(pos);
	return getans();
}

int updateY(int pos, int val) {
	add(1 , 1 , n , pos + 1 , pos + 1 , val);
	return getans();
}
/*
int main(){
int a[] = {2 , 1 , 3};
int b[] = {3 , 4 , 1};
}*/
// Author : حسن

Compilation message (stderr)

horses.cpp: In function 'long long int binpow(long long int, long long int)':
horses.cpp:56:21: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   56 | ll binpow(ll x , ll n){
      |                     ^
horses.cpp:54:12: note: shadowed declaration is here
   54 | ll f = 1 , n;
      |            ^
horses.cpp: In function 'long long int divmod(long long int, long long int)':
horses.cpp:65:21: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   65 | ll divmod(ll a , ll b){
      |                     ^
horses.cpp:23:11: note: shadowed declaration is here
   23 | ll a[N] , b[N] , d[N] , c[N] , dp[N] , t[4 * N];
      |           ^
horses.cpp:65:14: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   65 | ll divmod(ll a , ll b){
      |              ^
horses.cpp:23:4: note: shadowed declaration is here
   23 | ll a[N] , b[N] , d[N] , c[N] , dp[N] , t[4 * N];
      |    ^
horses.cpp: In function 'long long int mul(long long int, long long int)':
horses.cpp:68:18: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   68 | ll mul(ll a , ll b){
      |                  ^
horses.cpp:23:11: note: shadowed declaration is here
   23 | ll a[N] , b[N] , d[N] , c[N] , dp[N] , t[4 * N];
      |           ^
horses.cpp:68:11: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   68 | ll mul(ll a , ll b){
      |           ^
horses.cpp:23:4: note: shadowed declaration is here
   23 | ll a[N] , b[N] , d[N] , c[N] , dp[N] , t[4 * N];
      |    ^
horses.cpp: In function 'int getans()':
horses.cpp:81:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   81 |         l = get(1 , 1 , n , *it + 1 , r + 1 );
      |                         ^
horses.cpp:81:41: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   81 |         l = get(1 , 1 , n , *it + 1 , r + 1 );
      |                                       ~~^~~
horses.cpp:86:36: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   86 |             return ((x % mod) * k) % mod;
      |                    ~~~~~~~~~~~~~~~~^~~~~
horses.cpp:92:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   92 |     return (x % mod) * k % mod;
      |            ~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:95:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   95 | int init(int N, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:22:11: note: shadowed declaration is here
   22 | const int N = 5e5 + 9 , mod = 1e9 +7;
      |           ^
horses.cpp:102:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  102 |         add(1 , 1 , n , i + 1 , i + 1 , b[i]);
      |                     ^
horses.cpp:102:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  102 |         add(1 , 1 , n , i + 1 , i + 1 , b[i]);
      |                                         ~~~^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:121:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  121 |  add(1 , 1 , n , pos + 1 , pos + 1 , val);
      |              ^

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