Submission #293805

#	Time	Username	Problem	Language	Result	Execution time	Memory
293805		arayi	Horses (IOI15_horses)	C++17	57 / 100	1600 ms	37992 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
#define lli long long int
using namespace std;

const int N = 5e5 + 30;
const lli mod = 1e9 + 7;

lli bp(lli a, lli b = mod - 2)
{
    lli ret = 1;
    while(b)
    {
        if(b & 1) ret *= a, ret %= mod;
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return ret;
}
int n;
lli x[N], y[N], sum = 1;
lli t1[4 * N];
int t[4 * N];
void bld1(int l = 0, int r = n - 1, int nd = 1)
{
    if(l == r)
    {
        t1[nd] = y[l];
        return;
    }
    int mid = (l + r) / 2;
    bld1(l, mid, nd * 2);
    bld1(mid + 1, r, nd * 2 + 1);
    t1[nd] = max(t1[nd * 2], t1[nd * 2 + 1]);
}
void upd1(int q, int l = 0, int r = n - 1, int nd = 1)
{
    if(q > r || q < l) return;
    if(l == r)
    {
        t1[nd] = y[q];
        return;
    }
    int mid = (l + r) / 2;
    upd1(q, l, mid, nd * 2);
    upd1(q, mid + 1, r, nd * 2 + 1);
    t1[nd] = max(t1[nd * 2], t1[nd * 2 + 1]);
}
lli qry1(int l, int r, int nl = 0, int nr = n - 1, int nd = 1)
{
    if(l > nr || r < nl) return 0;
    if(l == nl && r == nr) return t1[nd];
    int mid = (nl + nr) / 2;
    return max(qry1(l, min(mid, r), nl, mid, nd * 2), qry1(max(l, mid + 1), r, mid + 1, nr, nd * 2 + 1));
}
void bld(int l = 0, int r = n - 1, int nd = 1)
{
    if(l == r)
    {
        t[nd] = l;
        if(x[l] == 1) t[nd] = 0;
        return;
    }
    int mid = (l + r) / 2;
    bld(l, mid, nd * 2);
    bld(mid + 1, r, nd * 2 + 1);
    t[nd] = max(t[nd * 2], t[nd * 2 + 1]);
}
void upd(int q, int l = 0, int r = n - 1, int nd = 1)
{
    if(q > r || q < l) return;
    if(l == r)
    {
        t[nd] = l;
        if(x[l] == 1) t[nd] = 0;
        return;
    }
    int mid = (l + r) / 2;
    upd(q, l, mid, nd * 2);
    upd(q, mid + 1, r, nd * 2 + 1);
    t[nd] = max(t[nd * 2], t[nd * 2 + 1]);
}
lli qry(int l, int r, int nl = 0, int nr = n - 1, int nd = 1)
{
    if(l > nr || r < nl) return 0;
    if(l == nl && r == nr) return t[nd];
    int mid = (nl + nr) / 2;
    return max(qry(l, min(mid, r), nl, mid, nd * 2), qry(max(l, mid + 1), r, mid + 1, nr, nd * 2 + 1));
}
lli slv()
{
    //cout << "SM" << endl;
    lli ss = sum, mx = 0, ret = 0;
    int i1 = n - 1;
    while(i1 >= 0 && mx < mod)
    {
        int ii = qry(0, i1);
        mx = max(mx, qry1(ii, i1));
        i1 = ii;
        mx *= x[i1];
        ss *= bp(x[ii]), ss %= mod;
        i1--;
    }
    return ((mx % mod) * ss) % mod;
}
int init(int N, int X[], int Y[])
{
	n = N;
	for (int i = 0; i < n; i++) x[i] = X[i], y[i] = Y[i], sum *= x[i], sum %= mod;
	bld();
    bld1();
    return slv();
}

int updateX(int pos, int val) {
    sum *= bp(x[pos]), sum %= mod;
    sum *= val, sum %= mod;
	x[pos] = val;
	upd(pos);
	return slv();
}

int updateY(int pos, int val) {
	y[pos] = val;
	upd1(pos);
	return slv();
}

Compilation message (stderr)

horses.cpp: In function 'long long int slv()':
horses.cpp:98:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   98 |         int ii = qry(0, i1);
      |                  ~~~^~~~~~~
horses.cpp:94:27: warning: unused variable 'ret' [-Wunused-variable]
   94 |     lli ss = sum, mx = 0, ret = 0;
      |                           ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:107:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  107 | int init(int N, int X[], int Y[])
      |                                 ^
horses.cpp:6:11: note: shadowed declaration is here
    6 | const int N = 5e5 + 30;
      |           ^
horses.cpp:113:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  113 |     return slv();
      |            ~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:121:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  121 |  return slv();
      |         ~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:127:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  127 |  return slv();
      |         ~~~^~

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