Submission #284385

#	Time	Username	Problem	Language	Result	Execution time	Memory
284385		SamAnd	Horses (IOI15_horses)	C++17	100 / 100	467 ms	68856 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int N = 500005, M = 1000000007;

int n;

struct ban
{
    int ans;
    int p;
    int pl, pr, pp;
    int y;
    ban()
    {
        ans = 1;
        p = 1;
        pl = 1;
        pr = 1;
    }
    ban(int x, int y)
    {
        ans = (x * 1LL * y) % M;
        p = x;
        pl = x;
        pr = 1;
        pp = x;
        this->y = y;
    }
};

ban t[N * 4];

ban mer(const ban& l, const ban& r)
{
    ban res;
    if (r.pl == M || l.pr == M)
    {
        res.ans = (l.p * 1LL * r.ans) % M;
        res.p = (l.p * 1LL * r.p) % M;
        res.pl = min(M * 1LL, l.pp * 1LL * r.pl);
        res.pr = r.pr;
        res.pp = min(M * 1LL, l.pp * 1LL * r.pp);
        res.y = r.y;
    }
    else
    {
        if ((long double)l.y / r.y < (r.pl * 1LL * l.pr))
        {
            res.ans = (l.p * 1LL * r.ans) % M;
            res.p = (l.p * 1LL * r.p) % M;
            res.pl = min(M * 1LL, l.pp * 1LL * r.pl);
            res.pr = r.pr;
            res.pp = min(M * 1LL, l.pp * 1LL * r.pp);
            res.y = r.y;
        }
        else
        {
            res.ans = l.ans;
            res.p = (l.p * 1LL * r.p) % M;
            res.pl = l.pl;
            res.pr = min(M * 1LL, l.pr * 1LL * r.pp);
            res.pp = min(M * 1LL, l.pp * 1LL * r.pp);
            res.y = l.y;
        }
    }
    return res;
}

void ubd(int tl, int tr, int x, int xx, int yy, int pos)
{
    if (tl == tr)
    {
        t[pos] = ban(xx, yy);
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(tl, m, x, xx, yy, pos * 2);
    else
        ubd(m + 1, tr, x, xx, yy, pos * 2 + 1);
    t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}

int X[N], Y[N];
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];
    }

    for (int i = 0; i < n; ++i)
        ubd(0, n - 1, i, X[i], Y[i], 1);

    return t[1].ans;
}

int updateX(int pos, int val)
{
    X[pos] = val;
    ubd(0, n - 1, pos, X[pos], Y[pos], 1);
	return t[1].ans;
}

int updateY(int pos, int val)
{
    Y[pos] = val;
    ubd(0, n - 1, pos, X[pos], Y[pos], 1);
	return t[1].ans;
}

Compilation message (stderr)

horses.cpp: In constructor 'ban::ban(int, int)':
horses.cpp:28:5: warning: declaration of 'y' shadows a member of 'ban' [-Wshadow]
   28 |     {
      |     ^
horses.cpp:19:9: note: shadowed declaration is here
   19 |     int y;
      |         ^
horses.cpp:29:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   29 |         ans = (x * 1LL * y) % M;
      |               ~~~~~~~~~~~~~~^~~
horses.cpp: In constructor 'ban::ban(int, int)':
horses.cpp:35:5: warning: declaration of 'y' shadows a member of 'ban' [-Wshadow]
   35 |     }
      |     ^
horses.cpp:19:9: note: shadowed declaration is here
   19 |     int y;
      |         ^
horses.cpp: In constructor 'ban::ban(int, int)':
horses.cpp:35:5: warning: declaration of 'y' shadows a member of 'ban' [-Wshadow]
   35 |     }
      |     ^
horses.cpp:19:9: note: shadowed declaration is here
   19 |     int y;
      |         ^
horses.cpp: In function 'ban mer(const ban&, const ban&)':
horses.cpp:45:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   45 |         res.ans = (l.p * 1LL * r.ans) % M;
      |                   ~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:46:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   46 |         res.p = (l.p * 1LL * r.p) % M;
      |                 ~~~~~~~~~~~~~~~~~~^~~
horses.cpp:47:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   47 |         res.pl = min(M * 1LL, l.pp * 1LL * r.pl);
      |                  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:49:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   49 |         res.pp = min(M * 1LL, l.pp * 1LL * r.pp);
      |                  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:56:43: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   56 |             res.ans = (l.p * 1LL * r.ans) % M;
      |                       ~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:57:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   57 |             res.p = (l.p * 1LL * r.p) % M;
      |                     ~~~~~~~~~~~~~~~~~~^~~
horses.cpp:58:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   58 |             res.pl = min(M * 1LL, l.pp * 1LL * r.pl);
      |                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:60:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   60 |             res.pp = min(M * 1LL, l.pp * 1LL * r.pp);
      |                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:66:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   66 |             res.p = (l.p * 1LL * r.p) % M;
      |                     ~~~~~~~~~~~~~~~~~~^~~
horses.cpp:68:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   68 |             res.pr = min(M * 1LL, l.pr * 1LL * r.pp);
      |                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:69:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   69 |             res.pp = min(M * 1LL, l.pp * 1LL * r.pp);
      |                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:92:34: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
   92 | int init(int N_, int X[], int Y[])
      |                                  ^
horses.cpp:91:11: note: shadowed declaration is here
   91 | int X[N], Y[N];
      |           ^
horses.cpp:92:34: warning: declaration of 'X' shadows a global declaration [-Wshadow]
   92 | int init(int N_, int X[], int Y[])
      |                                  ^
horses.cpp:91:5: note: shadowed declaration is here
   91 | int X[N], Y[N];
      |     ^

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