Submission #284367

#	Time	Username	Problem	Language	Result	Execution time	Memory
284367		SamAnd	말 (IOI15_horses)	C++17	17 / 100	307 ms	36600 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 pp;
    ban()
    {
        ans = 1;
        p = 1;
        pp = 1;
    }
    ban(int x, int y)
    {
        ans = (x * 1LL * y) % M;
        p = x;
        pp = x;
    }
};

ban t[N * 4];

ban mer(const ban& l, const ban& r)
{
    ban res;
    if (r.pp == M)
    {
        res.ans = (l.p * 1LL * r.ans) % M;
        res.p = (l.p * 1LL * r.p) % M;
        res.pp = M;
    }
    else
    {
        res.ans = max(l.ans * 1LL, l.p * 1LL * r.ans) % M;
        res.p = (l.p * 1LL * r.p) % M;
        res.pp = min(l.pp * 1LL * r.pp, M * 1LL);
    }
    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:27:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   27 |         ans = (x * 1LL * y) % M;
      |               ~~~~~~~~~~~~~~^~~
horses.cpp: In function 'ban mer(const ban&, const ban&)':
horses.cpp:40:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   40 |         res.ans = (l.p * 1LL * r.ans) % M;
      |                   ~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:41:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   41 |         res.p = (l.p * 1LL * r.p) % M;
      |                 ~~~~~~~~~~~~~~~~~~^~~
horses.cpp:46:55: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   46 |         res.ans = max(l.ans * 1LL, l.p * 1LL * r.ans) % M;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:47:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   47 |         res.p = (l.p * 1LL * r.p) % M;
      |                 ~~~~~~~~~~~~~~~~~~^~~
horses.cpp:48:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   48 |         res.pp = min(l.pp * 1LL * r.pp, M * 1LL);
      |                  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:69:34: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
   69 | int init(int N_, int X[], int Y[])
      |                                  ^
horses.cpp:68:11: note: shadowed declaration is here
   68 | int X[N], Y[N];
      |           ^
horses.cpp:69:34: warning: declaration of 'X' shadows a global declaration [-Wshadow]
   69 | int init(int N_, int X[], int Y[])
      |                                  ^
horses.cpp:68:5: note: shadowed declaration is here
   68 | int X[N], Y[N];
      |     ^

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