oj.uz

Submission #309531

# Submission time Handle Problem Language Result Execution time Memory
309531 2020-10-03T18:04:50 Z mihai145 Horses (IOI15_horses) C++14
100 / 100
 638 ms 65528 KB 
#include "horses.h"
#include <set>
#include <vector>
#include <algorithm>

const int YMAX = 1e9;
const int MOD = 1e9 + 7;
const int NMAX = 5e5;

int n;
long long x[NMAX + 2], y[NMAX + 2];

struct Aintx {
    long long v[4 * NMAX];

    void Build(int node, int st, int dr)
        {
            if(st == dr)
                {
                    v[node] = x[st];
                    return ;
                }

            int mid = (st + dr) >> 1;

            Build(2 * node, st, mid);
            Build(2 * node + 1, mid + 1, dr);

            v[node] = (1LL * v[2 * node] * v[2 * node + 1]) % MOD;
        }

    void setx(int node, int st, int dr, int pos, long long val)
        {
            if(st == dr)
                {
                    v[node] = val;
                    return;
                }

            int mid = (st + dr) >> 1;
            if(pos <= mid)
                setx(2 * node, st, mid, pos, val);
            else
                setx(2 * node + 1, mid + 1, dr, pos, val);

            v[node] = (1LL * v[2 * node] * v[2 * node + 1]) % MOD;
        }

    long long queryx(int node, int st, int dr, int l, int r)
        {
            if(l <= st && dr <= r)
                return v[node];

            if(dr < l || st > r)
                return 1;

            int mid = (st + dr) >> 1;
            long long ans1 = queryx(2 * node, st, mid, l, r);
            long long ans2 = queryx(2 * node + 1, mid + 1, dr, l, r);

            return (1LL * ans1 * ans2) % MOD;
        }
};
Aintx aintx;

struct Ainty {
    long long v[4 * NMAX];

    void Build(int node, int st, int dr)
        {
            if(st == dr)
                {
                    v[node] = y[st];
                    return ;
                }

            int mid = (st + dr) >> 1;

            Build(2 * node, st, mid);
            Build(2 * node + 1, mid + 1, dr);

            v[node] = std::max(v[2 * node], v[2 * node + 1]);
        }

    void sety(int node, int st, int dr, int pos, long long val)
        {
            if(st == dr)
                {
                    v[node] = val;
                    return;
                }

            int mid = (st + dr) >> 1;
            if(pos <= mid)
                sety(2 * node, st, mid, pos, val);
            else
                sety(2 * node + 1, mid + 1, dr, pos, val);

            v[node] = std::max(v[2 * node], v[2 * node + 1]);
        }

    long long queryy(int node, int st, int dr, int l, int r)
        {
            if(l <= st && dr <= r)
                return v[node];

            if(dr < l || st > r)
                return 1LL;

            int mid = (st + dr) >> 1;
            int ans1 = queryy(2 * node, st, mid, l, r);
            int ans2 = queryy(2 * node + 1, mid + 1, dr, l, r);

            return std::max(ans1, ans2);
        }
};
Ainty ainty;

std::set <int> s;

int Query()
{
    long long prod = 1LL;
    std::vector <int> pos;
    for(auto it : s)
        {
            if(prod >= YMAX)
                break;

            pos.push_back(-it);
            prod *= x[-it];
        }

    int sz = (int)pos.size();
    long long px = 1LL, py = 0, mx = 0;

    for(int i = sz - 2; i >= 0; i--)
        {
            px *= x[pos[i]];

            if(i > 0)
                py = ainty.queryy(1, 1, n, pos[i], pos[i - 1] - 1);
            else
                py = ainty.queryy(1, 1, n, pos[i], n);

            mx = std::max(mx, px * py);
        }

    if(pos.back() == 0)
        {
            py = ainty.queryy(1, 1, n, 1, n);
            return std::max(mx, py) % MOD;
        }

    if(sz > 1)
        py = ainty.queryy(1, 1, n, pos[sz - 1], pos[sz - 2] - 1);
    else
        py = ainty.queryy(1, 1, n, pos[sz - 1], n);

    long long f = std::max(mx, py) % MOD;
    return (1LL * f * aintx.queryx(1, 1, n, 1, pos[sz - 1])) % MOD;
}

int init(int N, int X[], int Y[]) {
    n = N;

    x[0] = 1LL;
    y[0] = 1LL;
    for(int i = 0; i < n; i++)
        x[i + 1] = 1LL * X[i], y[i + 1] = 1LL * Y[i];

    aintx.Build(1, 1, n);
    ainty.Build(1, 1, n);

    s.insert(0);
    for(int i = 1; i <= n; i++) {
        if(x[i] > 1) {
            s.insert(-i);
        }
    }

	return Query();
}

int updateX(int pos, int val) {
    pos++;
    if(x[pos] == val)
        return Query();

    aintx.setx(1, 1, n, pos, val);

    if(x[pos] > 1 && val == 1)
            s.erase(-pos);
    else if(x[pos] == 1 && val > 1)
            s.insert(-pos);

    x[pos] = 1LL * val;

	return Query();
}

int updateY(int pos, int val) {
    pos++;
    if(y[pos] == val)
        return Query();

    ainty.sety(1, 1, n, pos, val);
    y[pos] = 1LL * val;

	return Query();
}

Compilation message

horses.cpp: In member function 'long long int Ainty::queryy(int, int, int, int, int)':
horses.cpp:111:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  111 |             int ans1 = queryy(2 * node, st, mid, l, r);
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:112:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  112 |             int ans2 = queryy(2 * node + 1, mid + 1, dr, l, r);
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int Query()':
horses.cpp:152:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  152 |             return std::max(mx, py) % MOD;
      |                    ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:161:62: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  161 |     return (1LL * f * aintx.queryx(1, 1, n, 1, pos[sz - 1])) % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 0 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 2 ms 512 KB Output is correct
26 Correct 2 ms 512 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Correct 2 ms 512 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 2 ms 512 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 628 ms 53112 KB Output is correct
2 Correct 282 ms 52984 KB Output is correct
3 Correct 326 ms 52984 KB Output is correct
4 Correct 356 ms 53112 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 0 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 2 ms 512 KB Output is correct
26 Correct 1 ms 512 KB Output is correct
27 Correct 4 ms 384 KB Output is correct
28 Correct 2 ms 512 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 2 ms 512 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 55 ms 32632 KB Output is correct
34 Correct 55 ms 32632 KB Output is correct
35 Correct 210 ms 62968 KB Output is correct
36 Correct 195 ms 62840 KB Output is correct
37 Correct 98 ms 30844 KB Output is correct
38 Correct 115 ms 43512 KB Output is correct
39 Correct 42 ms 30584 KB Output is correct
40 Correct 187 ms 57960 KB Output is correct
41 Correct 66 ms 30656 KB Output is correct
42 Correct 80 ms 30712 KB Output is correct
43 Correct 170 ms 58488 KB Output is correct
44 Correct 174 ms 58360 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 288 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 2 ms 504 KB Output is correct
26 Correct 1 ms 512 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 2 ms 512 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 512 KB Output is correct
31 Correct 3 ms 512 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 627 ms 56824 KB Output is correct
34 Correct 286 ms 65528 KB Output is correct
35 Correct 321 ms 56824 KB Output is correct
36 Correct 350 ms 60664 KB Output is correct
37 Correct 55 ms 32632 KB Output is correct
38 Correct 53 ms 32632 KB Output is correct
39 Correct 206 ms 62972 KB Output is correct
40 Correct 196 ms 62840 KB Output is correct
41 Correct 95 ms 30840 KB Output is correct
42 Correct 117 ms 43640 KB Output is correct
43 Correct 42 ms 30584 KB Output is correct
44 Correct 182 ms 58104 KB Output is correct
45 Correct 64 ms 30584 KB Output is correct
46 Correct 83 ms 30712 KB Output is correct
47 Correct 173 ms 58360 KB Output is correct
48 Correct 175 ms 58360 KB Output is correct
49 Correct 189 ms 35704 KB Output is correct
50 Correct 167 ms 35576 KB Output is correct
51 Correct 349 ms 64888 KB Output is correct
52 Correct 235 ms 64376 KB Output is correct
53 Correct 638 ms 33964 KB Output is correct
54 Correct 307 ms 47480 KB Output is correct
55 Correct 132 ms 31608 KB Output is correct
56 Correct 286 ms 59792 KB Output is correct
57 Correct 351 ms 32376 KB Output is correct
58 Correct 514 ms 32760 KB Output is correct
59 Correct 175 ms 58360 KB Output is correct