Submission #1201345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201345		notme	Horses (IOI15_horses)	C++20	37 / 100	519 ms	61272 KiB

horses

#include<bits/stdc++.h>
#define pb push_back
#include "horses.h"
using namespace std;
const int maxn = 5e5 + 10;
const long long mod = 1e9 + 7;
long long n, a[maxn], b[maxn];
long long t[maxn * 4], ti[maxn * 4], tg[maxn * 4];
void build(int i, int l, int r)
{
    t[i] = b[l];
    ti[i] = l;
    tg[i] = a[l];
    if(l == r)return;
    int mid = (l + r)/2;
    build(2*i, l, mid);
    build(2*i+1, mid+1, r);
    t[i] = max(t[2*i], t[2*i+1]);
    if(t[2*i] > t[2*i+1])ti[i] = ti[2*i];
    else ti[i] = ti[2*i+1];
    tg[i] = tg[2*i] * tg[2*i+1];
    tg[i] %= mod;
}
long long  updpos, updval;
void update_prod(int i, int l, int r)
{
    if(l == r)
    {
        tg[i] = updval;
        a[l] = updval;
        return;
    }
    int mid = (l + r)/2;
    if(updpos <= mid)update_prod(2*i, l, mid);
    else update_prod(2*i+1, mid+1, r);
    tg[i] = 1LL * tg[2*i] * tg[2*i+1];
    tg[i] %= mod;
}
void update_max(int i, int l, int r)
{
    if(l == r)
    {
        b[l] = updval;
        ti[i] = l;
        t[i] = b[l];
        return;
    }
    int mid = (l + r)/2;
    if(updpos <= mid)update_max(2*i, l, mid);
    else update_max(2*i+1, mid+1, r);
    t[i] = max(t[2*i], t[2*i+1]);
    if(t[2*i] > t[2*i+1])ti[i] = ti[2*i];
    else ti[i] = ti[2*i+1];
}
int ql, qr;
long long query_prod(int i, int l, int r)
{
    if(l > r)return 1;
    if(ql > r || qr < l)return 1;
    if(ql <= l && r <= qr)return tg[i];
    int mid = (l + r)/2;
    long long pos1 = query_prod(2*i, l, mid);
    long long pos2 = query_prod(2*i+1, mid+1, r);
    return (pos1 * pos2) % mod;
}
long long query_max(int i, int l, int r)
{
    if(l > r)return 0;
    if(ql > r || qr < l)return 0;
    if(ql <= l && r <= qr)return ti[i];
    int mid = (l + r)/2;
    int pos1 = query_max(2*i, l, mid);
    int pos2 = query_max(2*i+1, mid+1, r);
    if(!pos1 || !pos2)return (pos1 + pos2);
    if(b[pos1] > b[pos2])return pos1;
    else return pos2;
}


set < int > s;
int cnt = 0;
long long solve()
{
    cnt ++;
    if(s.size() == 0)
    {
        ql = 1;
       qr = n;
       // cout << pos << " " << n << endl;
       return b[query_max(1, 1, n)];
    }
    s.insert(1);
    set < int >::iterator it = s.end();
    long long best = 0, bestsell = 0, index = 1;
    while(it != s.begin())
    {
        int pre = n;
        if(it != s.end())pre = *it - 1;

        it --;


        long long pos = *it;
       // if(cnt < 10)cout << pre << " " << pos << endl;
        ql = pos;
        qr = pre;
        long long sell = b[query_max(1, 1, n)];
       // if(cnt < 10)cout << "sell is " << sell << endl;
        if(sell > best)
        {
            best = sell;
            index = pos;
            bestsell = sell;
        }
        best *= a[pos];
        if(best > 1LL * 1e9)break;

    }
    s.erase(1);
      //  cout << bestprod << " " << bestsell << endl;
      ql = 1;
      qr = index;
    return 1LL * (bestsell * query_prod(1, 1, n))%mod;

}
int init(int N, int X[], int Y[])
{
    n = N;
    for (int i = 0; i < n; ++ i)
        a[i+1] = X[i];
    for (int i = 0; i < n; ++ i)
        b[i+1] = Y[i];
    build(1, 1, n);
    for (int i = 1; i <= n; ++ i)
        if(a[i] > 1)s.insert(i);

    long long ans =  solve();
    //cout << "ans s " << ans << endl;
    return ans;
}

int updateX(int pos, int val)
{
    pos ++;
    if(a[pos] > 1)s.erase(pos);
    updpos = pos;
    updval = val;
    update_prod(1, 1, n);
    if(val > 1)s.insert(pos);
	return solve();
}

int updateY(int pos, int val)
{
    pos ++;
    b[pos] = val;
    updpos = pos;
    updval = val;
    update_max(1, 1, n);
	return solve();
}

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