oj.uz

Submission #710649

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

using namespace std;

#define MOD 1000000007

int ng;

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(500000, 1, -1, mergex, updx, 0);
LazySegmentTree<long long> sty(500000, 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]);
        if(x[i] > 1)
        {
            s.insert(i);
        }
        sty.modif(i, y[i]);
    }
    auto it = s.end();
    it--;
    while(true)
    {
        if(*it != ng && stx.query(*it, ng-1) > 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*=stx.query(*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);
        stx.modif(pos, val);
    }
    else if(stx.query(pos) != 1 && val == 1)
    {
        s.erase(s.find(pos));
        stx.modif(pos, val);
    }
    auto it = s.end();
    it--;
    while(true)
    {
        if(*it != ng && stx.query(*it, ng-1) > 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*=stx.query(*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--;
    while(true)
    {
        if(*it != ng && stx.query(*it, ng-1) > 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*=stx.query(*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:113:26: warning: unused parameter 'a' [-Wunused-parameter]
  113 | 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:123:26: warning: unused parameter 'a' [-Wunused-parameter]
  123 | long long updy(long long a, long long b)
      |                ~~~~~~~~~~^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62932 KB Output is correct
2 Correct 26 ms 62932 KB Output is correct
3 Correct 24 ms 62932 KB Output is correct
4 Correct 24 ms 62856 KB Output is correct
5 Correct 32 ms 62812 KB Output is correct
6 Correct 24 ms 62924 KB Output is correct
7 Correct 24 ms 62868 KB Output is correct
8 Correct 24 ms 62852 KB Output is correct
9 Correct 24 ms 62844 KB Output is correct
10 Correct 27 ms 62932 KB Output is correct
11 Correct 24 ms 62932 KB Output is correct
12 Correct 25 ms 62924 KB Output is correct
13 Correct 27 ms 62860 KB Output is correct
14 Correct 24 ms 62932 KB Output is correct
15 Correct 24 ms 62828 KB Output is correct
16 Correct 28 ms 62900 KB Output is correct
17 Correct 24 ms 62936 KB Output is correct
18 Correct 24 ms 62932 KB Output is correct
19 Correct 26 ms 62932 KB Output is correct
20 Correct 25 ms 62860 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62912 KB Output is correct
2 Correct 27 ms 62864 KB Output is correct
3 Correct 26 ms 62888 KB Output is correct
4 Correct 25 ms 62920 KB Output is correct
5 Correct 25 ms 62932 KB Output is correct
6 Correct 26 ms 62924 KB Output is correct
7 Correct 25 ms 62920 KB Output is correct
8 Correct 24 ms 62864 KB Output is correct
9 Correct 26 ms 62944 KB Output is correct
10 Correct 25 ms 62924 KB Output is correct
11 Correct 24 ms 62928 KB Output is correct
12 Correct 25 ms 62924 KB Output is correct
13 Correct 26 ms 62932 KB Output is correct
14 Correct 25 ms 62892 KB Output is correct
15 Correct 24 ms 62916 KB Output is correct
16 Correct 25 ms 62896 KB Output is correct
17 Correct 25 ms 62804 KB Output is correct
18 Correct 23 ms 62932 KB Output is correct
19 Correct 25 ms 62872 KB Output is correct
20 Correct 24 ms 62860 KB Output is correct
21 Incorrect 24 ms 62840 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1570 ms 90356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62932 KB Output is correct
2 Correct 25 ms 62848 KB Output is correct
3 Correct 24 ms 62836 KB Output is correct
4 Correct 24 ms 62932 KB Output is correct
5 Correct 24 ms 62932 KB Output is correct
6 Correct 25 ms 62944 KB Output is correct
7 Correct 24 ms 62840 KB Output is correct
8 Correct 25 ms 62932 KB Output is correct
9 Correct 27 ms 62800 KB Output is correct
10 Correct 26 ms 62932 KB Output is correct
11 Correct 25 ms 62884 KB Output is correct
12 Correct 26 ms 62888 KB Output is correct
13 Correct 28 ms 62936 KB Output is correct
14 Correct 24 ms 62932 KB Output is correct
15 Correct 25 ms 62992 KB Output is correct
16 Correct 24 ms 62864 KB Output is correct
17 Correct 26 ms 62836 KB Output is correct
18 Correct 25 ms 62920 KB Output is correct
19 Correct 28 ms 62864 KB Output is correct
20 Correct 25 ms 62896 KB Output is correct
21 Incorrect 26 ms 62928 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 62876 KB Output is correct
2 Correct 24 ms 62832 KB Output is correct
3 Correct 26 ms 62852 KB Output is correct
4 Correct 26 ms 62888 KB Output is correct
5 Correct 25 ms 62852 KB Output is correct
6 Correct 24 ms 62932 KB Output is correct
7 Correct 24 ms 62872 KB Output is correct
8 Correct 25 ms 62800 KB Output is correct
9 Correct 24 ms 62932 KB Output is correct
10 Correct 28 ms 62840 KB Output is correct
11 Correct 25 ms 62892 KB Output is correct
12 Correct 28 ms 62836 KB Output is correct
13 Correct 28 ms 62904 KB Output is correct
14 Correct 24 ms 62932 KB Output is correct
15 Correct 29 ms 62864 KB Output is correct
16 Correct 25 ms 62900 KB Output is correct
17 Correct 25 ms 62864 KB Output is correct
18 Correct 24 ms 62928 KB Output is correct
19 Correct 24 ms 62816 KB Output is correct
20 Correct 26 ms 62884 KB Output is correct
21 Incorrect 25 ms 62832 KB Output isn't correct
22 Halted 0 ms 0 KB -