Submission #298831

#	Time	Username	Problem	Language	Result	Execution time	Memory
298831		davooddkareshki	Horses (IOI15_horses)	C++17	57 / 100	1559 ms	104696 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 = 5e5+2;
const int mod = 1e9+7;
const ll inf = 1e9+10;

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

int x[maxn], y[maxn];
struct segment_Y
{
    int mx[maxn<<2];
    void build(int v = 1, int tl = 1, int tr = n)
    {
        if(tl == tr)
        {
            mx[v] = y[tl];
            return;
        }

        int tm = (tl + tr) >> 1;
        build(v<<1, tl, tm);
        build(v<<1|1, tm+1, tr);
        mx[v] = max(mx[v<<1], mx[v<<1|1]);
    }

    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];
    void build(int v = 1, int tl = 1, int tr = n)
    {
        if(tl == tr)
        {
            mul[v] = x[tl];
            return;
        }

        int tm = (tl + tr) >> 1;
        build(v<<1, tl, tm);
        build(v<<1|1, tm+1, tr);
        mul[v] = (mul[v<<1] * 1ll * mul[v<<1|1]) % mod;
    }

    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<<2];
void buildX(int v = 1, int tl = 1, int tr = n)
{
    if(tl == tr)
    {
        if(x[tl] >= 2) seg[v].push_back(tl);
        return;
    }

    int tm = (tl + tr) >> 1;
    buildX(v<<1, tl, tm);
    buildX(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();
}
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])
    {
        if((int)seg[v].size() > 30) break;
        seg[v].push_back(x);
    }
    for(auto x : seg[v<<1])
    {
        if((int)seg[v].size() > 30) break;
        seg[v].push_back(x);
    }
}

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);
    }

    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()];
    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];
    }
    seg_X.build();
    seg_Y.build();
    buildX();
    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::build(int, int, int)':
horses.cpp:77:50: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   77 |         mul[v] = (mul[v<<1] * 1ll * mul[v<<1|1]) % mod;
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'void segment_X::change(int, int, int, int, int)':
horses.cpp:91:50: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   91 |         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:101:55: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  100 |         return (qu(l, min(tm,r), v<<1, tl, tm) * 1ll *
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
  101 |                 qu(max(tm+1,l), r, v<<1|1, tm+1, tr)) % mod;
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void buildX(int, int, int)':
horses.cpp:120:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  120 |     for(auto x : seg[v<<1|1]) seg[v].push_back(x);
      |              ^
horses.cpp:20:5: note: shadowed declaration is here
   20 | int x[maxn], y[maxn];
      |     ^
horses.cpp:121:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  121 |     for(auto x : seg[v<<1])   seg[v].push_back(x);
      |              ^
horses.cpp:20:5: note: shadowed declaration is here
   20 | int x[maxn], y[maxn];
      |     ^
horses.cpp: In function 'void updX(int, int, int, int, int)':
horses.cpp:139:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  139 |     for(auto x : seg[v<<1|1])
      |              ^
horses.cpp:20:5: note: shadowed declaration is here
   20 | int x[maxn], y[maxn];
      |     ^
horses.cpp:144:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  144 |     for(auto x : seg[v<<1])
      |              ^
horses.cpp:20:5: note: shadowed declaration is here
   20 | int x[maxn], y[maxn];
      |     ^
horses.cpp: In function 'int mul(int, int)':
horses.cpp:151:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  151 | int mul(int a, int b) {return min(a*1ll*b,inf);}
      |                               ~~~^~~~~~~~~~~~~
horses.cpp: In function 'int answer()':
horses.cpp:191:51: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  191 |     return (seg_X.qu(1,id) * 1ll * Y[YES.back()]) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:195:33: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
  195 | int init(int N, int X[], int Y[])
      |                                 ^
horses.cpp:154:15: note: shadowed declaration is here
  154 | vector<int> X,Y;
      |               ^
horses.cpp:195:33: warning: declaration of 'X' shadows a global declaration [-Wshadow]
  195 | int init(int N, int X[], int Y[])
      |                                 ^
horses.cpp:154:13: note: shadowed declaration is here
  154 | vector<int> X,Y;
      |             ^

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