Submission #1201072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201072		notme	Horses (IOI15_horses)	C++20	0 / 100	483 ms	57184 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;
int 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;
}
int 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] = 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;
int 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;
    int pos1 = query_prod(2*i, l, mid);
    int pos2 = query_prod(2*i+1, mid+1, r);
    return (pos1 * pos2) % mod;
}
int 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;
long long solve()
{
    if(s.size() == 1)
    {
         ql = 1;
       qr = n;
       // cout << pos << " " << n << endl;
       return b[query_max(1, 1, n)];
    }
    long long bestprod = 1, bestsell = 1;
    long long currprod = 1, currsell = 1;
    set < int >::iterator it = s.begin();
    long long last= 1;
    for (it = s.begin(); it != s.end(); it ++)
    {
        int pos = *it;
        currprod *= a[pos];

       ql = pos;
       qr = n;
       // cout << pos << " " << n << endl;
       currsell = b[query_max(1, 1, n)];


        //cout << currprod << " ... " << currsell << endl;
       if(currprod > 1e9)
       {

           set < int >::reverse_iterator iter = s.rbegin();

           ql = *iter;
           qr = n;
           long long csell = b[query_max(1, 1, n)] % mod;
           ql = 1;
           qr = *iter;
           long long cprod = query_prod(1, 1, n) % mod;
           return (csell * cprod)%mod;
       }

        if(bestprod * bestsell < currprod * currsell)
        {
           // cout << "here?" << endl;
            bestprod = currprod;
            bestsell = currsell;
           // cout << bestprod << " " << bestsell << endl;
        }
        last = pos;
       // currprod *= a[pos];
    }
    if(bestprod * bestsell < currprod * currsell)
        {
            bestprod = currprod;
            bestsell = currsell;
        }
      //  cout << bestprod << " " << bestsell << endl;
    return (bestprod * bestsell)%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: 0 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23