oj.uz

Submission #710655

# Submission time Handle Problem Language Result Execution time Memory
710655 2023-03-15T13:41:12 Z ssense Horses (IOI15_horses) C++14
17 / 100
 1500 ms 30140 KB 
#include <bits/stdc++.h>
#include "horses.h"

using namespace std;

#define MOD 1000000007

int ng;
vector<int> xg;

long long power(long long n, long long pow, long long m) {if (pow == 0) return 1;if (pow % 2 == 0) {long long x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;}

template<typename T>
struct LazySegmentTree{
    int n;
    vector<T> t, lazy, a;
    T neutral, lazy_neutral;
    function<T(const T&, const T&)> merge;
    function<T(const T&, const T&)> upd;
    
    bool range_modif = false;
    LazySegmentTree(int _n, T _neutral, T _lazy_neutral, const function<T(const T&, const T&)> &_merge, const function<T(const T&, const T&)> &_upd, bool _range_modif){
        range_modif = _range_modif;
        init(_n, _neutral, _lazy_neutral, _merge, _upd);
    }
    LazySegmentTree(vector<T> _a, T _neutral, T _lazy_neutral, const function<T(const T&, const T&)> &_merge, const function<T(const T&, const T&)> &_upd, bool _range_modif){
        range_modif = _range_modif, a = _a;
        int _n = (int)a.size();
        init(_n, _neutral, _lazy_neutral, _merge, _upd);
        build(1, 0, n - 1);
    }
    
    void init(int _n, T _neutral, T _lazy_neutral, const function<T(const T&, const T&)> &_merge, const function<T(const T&, const T&)> &_upd){
        n = _n, neutral = _neutral, lazy_neutral = _lazy_neutral, merge = _merge, upd = _upd;
        t.assign(4 * n, neutral);
        lazy.assign(4 * n, lazy_neutral);
    }
    
    void build(int i, int l, int r){
        if(l == r){
            t[i] = a[l];
            return;
        }
        
        int mid = (l + r) >> 1;
        build(2 * i, l, mid);
        build(2 * i + 1, mid + 1, r);
        
        t[i] = merge(t[2 * i], t[2 * i + 1]);
    }
    
    void push(int i, int l, int r){
        if(lazy[i] == lazy_neutral)return;
        
        t[i] = upd(t[i], lazy[i] * (range_modif ? (r - l + 1) : 1));
        
        if(l != r){
            lazy[2 * i] = upd(lazy[2 * i], lazy[i]);
            lazy[2 * i + 1] = upd(lazy[2 * i + 1], lazy[i]);
        }
        lazy[i] = lazy_neutral;
    }
    
    void modif(int i, int l, int r, int tl, int tr, T val){
        push(i, l, r);
        if(l > tr || r < tl)return;
        
        if(l >= tl && r <= tr){
            lazy[i] = upd(lazy[i], val);
            push(i, l, r);
            return;
        }
        
        int mid = (l + r) >> 1;
        
        modif(2 * i, l, mid, tl, tr, val);
        modif(2 * i + 1, mid + 1, r, tl, tr, val);
        
        t[i] = merge(t[2 * i], t[2 * i + 1]);
    }
    T query(int i, int l, int r, int tl, int tr){
        push(i, l, r);
        if(l > tr || r < tl)return neutral;
        if(l >= tl && r <= tr)return t[i];
        
        int mid = (l + r) >> 1;
        
        T left = query(2 * i, l, mid, tl, tr);
        T right = query(2 * i + 1, mid + 1, r, tl, tr);
        
        return merge(left, right);
    }
    
    void modif(int l, int r, T val){
        modif(1, 0, n - 1, l, r, val);
    }
    void modif(int poz, T val){
        modif(1, 0, n - 1, poz, poz, val);
    }
    T query(int l, int r){
        return query(1, 0, n - 1, l, r);
    }
    T query(int poz){
        return query(1, 0, n - 1, poz, poz);
    }
    //n, neutral, lazy neutral, merge, upd, bool range update
};

long long mergex(long long a, long long b)
{
    return (a*b)%MOD;
}

long long updx(long long a, long long b)
{
    return b;
}

long long mergey(long long a, long long b)
{
    return max(a, b);
}

long long updy(long long a, long long b)
{
    return b;
}

LazySegmentTree<long long> stx(2000, 1, -1, mergex, updx, 0);
LazySegmentTree<long long> sty(2000, 0, -1, mergey, updy, 0);

set<int> s;

int init(int n, int* x, int* y)
{
    ng = n;
    s.insert(0);
    s.insert(ng);
    for(int i = 0; i < ng; i++)
    {
        stx.modif(i, x[i]);
        xg.push_back(x[i]);
        if(x[i] > 1)
        {
            s.insert(i);
        }
        sty.modif(i, y[i]);
    }
    auto it = s.end();
    it--;
    long long pref = 1;
    while(true)
    {
        if(*it == ng)
        {
            it--;
            continue;
        }
        pref*=xg[*it];
        if(pref > 1000000000)
        {
            break;
        }
        if(it == s.begin())
        {
            break;
        }
        it--;
    }
    auto first = it;
    long long should_multiply = stx.query(0LL, *it);
    long long now = 1;
    long long mx = 0;
    for(; it != s.end(); it++)
    {
        if(it != first)
        {
            now*=xg[*it];
        }
        auto urmatorul = it;
        urmatorul++;
        if(urmatorul == s.end()){break;}
        long long now_range = now*sty.query(*it, (*urmatorul)-1);
        mx = max(mx, now_range);
    }
    mx%=MOD;
    return (int)((mx*should_multiply)%MOD);
}

int updateX(int pos, int val)
{
    if(stx.query(pos) == 1 && val != 1)
    {
        s.insert(pos);
    }
    else if(stx.query(pos) != 1 && val == 1)
    {
        s.erase(s.find(pos));
    }
    xg[pos] = val;
    stx.modif(pos, val);
    auto it = s.end();
    it--;
    long long pref = 1;
    while(true)
    {
        if(*it == ng)
        {
            it--;
            continue;
        }
        pref*=xg[*it];
        if(pref > 1000000000)
        {
            break;
        }
        if(it == s.begin())
        {
            break;
        }
        it--;
    }
    auto first = it;
    long long should_multiply = stx.query(0LL, *it);
    long long now = 1;
    long long mx = 0;
    for(; it != s.end(); it++)
    {
        if(it != first)
        {
            now*=xg[*it];
        }
        auto urmatorul = it;
        urmatorul++;
        if(urmatorul == s.end()){break;}
        long long now_range = now*sty.query(*it, *urmatorul-1);
        mx = max(mx, now_range);
    }
    mx%=MOD;
    return (int)((mx*should_multiply)%MOD);
}

int updateY(int pos, int val)
{
    sty.modif(pos, val);
    auto it = s.end();
    it--;
    long long pref = 1;
    while(true)
    {
        if(*it == ng)
        {
            it--;
            continue;
        }
        pref*=xg[*it];
        if(pref > 1000000000)
        {
            break;
        }
        if(it == s.begin())
        {
            break;
        }
        it--;
    }
    auto first = it;
    long long should_multiply = stx.query(0LL, *it);
    long long now = 1;
    long long mx = 0;
    for(; it != s.end(); it++)
    {
        if(it != first)
        {
            now*=xg[*it];
        }
        auto urmatorul = it;
        urmatorul++;
        if(urmatorul == s.end()){break;}
        long long now_range = now*sty.query(*it, *urmatorul-1);
        mx = max(mx, now_range);
    }
    mx%=MOD;
    return (int)((mx*should_multiply)%MOD);
}

Compilation message

horses.cpp: In function 'long long int updx(long long int, long long int)':
horses.cpp:114:26: warning: unused parameter 'a' [-Wunused-parameter]
  114 | long long updx(long long a, long long b)
      |                ~~~~~~~~~~^
horses.cpp: In function 'long long int updy(long long int, long long int)':
horses.cpp:124:26: warning: unused parameter 'a' [-Wunused-parameter]
  124 | long long updy(long long a, long long b)
      |                ~~~~~~~~~~^

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 0 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 3 ms 468 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 3 ms 596 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 7 ms 584 KB Output is correct
28 Correct 3 ms 596 KB Output is correct
29 Execution timed out 1592 ms 572 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 30140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 0 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 3 ms 468 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 4 ms 596 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 9 ms 468 KB Output is correct
28 Correct 4 ms 596 KB Output is correct
29 Execution timed out 1580 ms 468 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 472 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 472 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 2 ms 596 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 3 ms 596 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 8 ms 588 KB Output is correct
28 Correct 6 ms 596 KB Output is correct
29 Execution timed out 1583 ms 468 KB Time limit exceeded
30 Halted 0 ms 0 KB -