Submission #298818

#	Time	Username	Problem	Language	Result	Execution time	Memory
298818		davooddkareshki	Horses (IOI15_horses)	C++17	34 / 100	1592 ms	188756 KiB

horses

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

using namespace std;

typedef long long ll;
//#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair

const int maxn = 1e6+10;
const int mod = 1e9+7;
const ll inf = 1e9+10;

int n;
/// baraye Y --> tagir yek adad va maximom yek baze

struct segment_Y
{
    int mx[maxn<<2];
    segment_Y() {memset(mx, 0, sizeof mx);}
    void change(int pos, int val, int v = 1, int tl = 1, int tr = n)
    {
        if(tl == tr)
        {
            mx[v] = val;
            return;
        }

        int tm = (tl + tr) >> 1;
        if(pos <= tm) change(pos, val, v<<1, tl, tm);
        else          change(pos, val, v<<1|1, tm+1, tr);
        mx[v] = max(mx[v<<1],mx[v<<1|1]);
    }

    int qu(int l, int r, int v = 1, int tl = 1, int tr = n)
    {
        if(l > r) return 1;
        if(tl == l && tr == r) return mx[v];

        int tm = (tl + tr) >> 1;
        return max(qu(l, min(tm,r), v<<1, tl, tm),
                    qu(max(tm+1,l), r, v<<1|1, tm+1, tr));
    }
} seg_Y;

struct segment_X
{
    int mul[maxn<<2];
    segment_X() {fill(mul, mul+4*maxn, 1);}
    void change(int pos, int val, int v = 1, int tl = 1, int tr = n)
    {
        if(tl == tr)
        {
            mul[v] = val;
            return;
        }

        int tm = (tl + tr) >> 1;
        if(pos <= tm) change(pos, val, v<<1, tl, tm);
        else          change(pos, val, v<<1|1, tm+1, tr);
        mul[v] = (mul[v<<1] * 1ll * mul[v<<1|1]) % mod;
    }

    int qu(int l, int r, int v = 1, int tl = 1, int tr = n)
    {
        if(l > r) return 1;
        if(tl == l && tr == r) return mul[v];

        int tm = (tl + tr) >> 1;
        return (qu(l, min(tm,r), v<<1, tl, tm) * 1ll *
                qu(max(tm+1,l), r, v<<1|1, tm+1, tr)) % mod;
    }
} seg_X;

vector<int> seg[maxn];
void updX(int pos, int val, int v = 1, int tl = 1, int tr = n)
{
    if(tl == tr)
    {
        seg[v].clear();
        if(val >= 2) seg[v].push_back(tl);
        return;
    }

    int tm = (tl + tr) >> 1;
    if(pos <= tm) updX(pos, val, v<<1, tl, tm);
    else          updX(pos, val, v<<1|1, tm+1, tr);

    /// seg[v] nozolie
    seg[v].clear();
    for(auto x : seg[v<<1|1]) seg[v].push_back(x);
    for(auto x : seg[v<<1])   seg[v].push_back(x);
    while((int)seg[v].size() > 32ll) seg[v].pop_back();
}

int x[maxn], y[maxn];
int mul(int a, int b) {return min(a*1ll*b,inf);}
int mult[33][33];

vector<int> X,Y;
bool cmp(int i, int j)
{
    bool sw = 0;
    if(i > j) {sw = 1; swap(i,j);}

    return (sw ^ (Y[i] < mul(mult[i+1][j],Y[j])));
}
int answer()
{
    vector<int> ve = seg[1];
    bool DO = 0;
    if(ve.empty()) DO = 1;
    else if(ve.back() > 1) DO = 1;
    if(DO) ve.push_back(1);

    reverse(ve.begin(), ve.end());
    X.clear(); Y.clear();

    vector<int> YES;
    for(int i = 0; i < (int)ve.size(); i++)
    {
        X.push_back(x[ve[i]]);
        Y.push_back(seg_Y.qu(ve[i],n));
        YES.push_back(i);
        //cout<< ve[i] <<" "<< X.back() <<" "<< Y.back() <<"\n";
    }
    //cout<<"\n";

    for(int i = 0; i < 33; i++) for(int j = 0; j < 33; j++) mult[i][j] = 1;
    for(int l = 0; l < (int)X.size(); l++)
    {
        mult[l][l] = X[l];
        for(int r = l+1; r < (int)X.size(); r++)
            mult[l][r] = mul(mult[l][r-1],X[r]);
    }

    sort(YES.begin(), YES.end(), cmp);
    int id = ve[YES.back()];
    //cout<< id <<"\n";
    //cout<< y[id] <<"\n";
    return (seg_X.qu(1,id) * 1ll * Y[YES.back()]) % mod;
}


int init(int N, int X[], int Y[])
{
    n = N;
    x[0] = 1; y[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        x[i] = X[i-1];
        y[i] = Y[i-1];
        updX(i,x[i]);
        seg_X.change(i,x[i]);
        seg_Y.change(i,y[i]);
    }
    return answer();
}

int updateX(int pos, int val)
{
    pos++;
    x[pos] = val;
    updX(pos,val);
    seg_X.change(pos,val);
    return answer();
}

int updateY(int pos, int val)
{
    pos++;
    y[pos] = val;
    seg_Y.change(pos,val);
    return answer();
}
/*
int arrX[3] = {2,1,3};
int arrY[3] = {3,4,1};
signed main()
{
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cout<< init(3, arrX, arrY) <<"\n";
    cout<< updateY(1,2) <<"\n";
}
*/

Compilation message (stderr)

horses.cpp: In member function 'void segment_X::change(int, int, int, int, int)':
horses.cpp:64:50: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   64 |         mul[v] = (mul[v<<1] * 1ll * mul[v<<1|1]) % mod;
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'int segment_X::qu(int, int, int, int, int)':
horses.cpp:74:55: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   73 |         return (qu(l, min(tm,r), v<<1, tl, tm) * 1ll *
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
   74 |                 qu(max(tm+1,l), r, v<<1|1, tm+1, tr)) % mod;
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int mul(int, int)':
horses.cpp:100:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  100 | int mul(int a, int b) {return min(a*1ll*b,inf);}
      |                               ~~~^~~~~~~~~~~~~
horses.cpp: In function 'int answer()':
horses.cpp:144:51: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  144 |     return (seg_X.qu(1,id) * 1ll * Y[YES.back()]) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:148:33: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
  148 | int init(int N, int X[], int Y[])
      |                                 ^
horses.cpp:103:15: note: shadowed declaration is here
  103 | vector<int> X,Y;
      |               ^
horses.cpp:148:33: warning: declaration of 'X' shadows a global declaration [-Wshadow]
  148 | int init(int N, int X[], int Y[])
      |                                 ^
horses.cpp:103:13: note: shadowed declaration is here
  103 | vector<int> X,Y;
      |             ^

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