oj.uz

답안 #710638

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
710638 2023-03-15T12:53:38 Z ssense 말 (IOI15_horses) C++14
17 / 100
 1500 ms 90328 KB 
#include <bits/stdc++.h>
#include "horses.h"

using namespace std;

#define MOD 1000000007

int ng;
vector<long long> xg;
vector<long long> yg;
long long pref = 1;

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, 0, mergex, updx, 0);
LazySegmentTree<long long> sty(500000, 0, 0, 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 < n; 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(stx.query(*it, n-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(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(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: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

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 62796 KB Output is correct
2 Correct 26 ms 62820 KB Output is correct
3 Correct 26 ms 62936 KB Output is correct
4 Correct 26 ms 62956 KB Output is correct
5 Correct 27 ms 62924 KB Output is correct
6 Correct 26 ms 62900 KB Output is correct
7 Correct 25 ms 62820 KB Output is correct
8 Correct 25 ms 62808 KB Output is correct
9 Correct 28 ms 62840 KB Output is correct
10 Correct 30 ms 62860 KB Output is correct
11 Correct 25 ms 62932 KB Output is correct
12 Correct 25 ms 62848 KB Output is correct
13 Correct 26 ms 62924 KB Output is correct
14 Correct 28 ms 62908 KB Output is correct
15 Correct 25 ms 62816 KB Output is correct
16 Correct 25 ms 62944 KB Output is correct
17 Correct 27 ms 62944 KB Output is correct
18 Correct 26 ms 62872 KB Output is correct
19 Correct 26 ms 62864 KB Output is correct
20 Correct 25 ms 62892 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 62880 KB Output is correct
2 Correct 28 ms 62808 KB Output is correct
3 Correct 29 ms 62916 KB Output is correct
4 Correct 29 ms 62856 KB Output is correct
5 Correct 25 ms 62932 KB Output is correct
6 Correct 30 ms 62916 KB Output is correct
7 Correct 28 ms 62900 KB Output is correct
8 Correct 29 ms 62928 KB Output is correct
9 Correct 26 ms 62868 KB Output is correct
10 Correct 26 ms 62916 KB Output is correct
11 Correct 25 ms 62876 KB Output is correct
12 Correct 28 ms 62892 KB Output is correct
13 Correct 27 ms 62840 KB Output is correct
14 Correct 26 ms 62804 KB Output is correct
15 Correct 25 ms 62956 KB Output is correct
16 Correct 24 ms 62900 KB Output is correct
17 Correct 25 ms 62888 KB Output is correct
18 Correct 25 ms 62948 KB Output is correct
19 Correct 25 ms 62924 KB Output is correct
20 Correct 25 ms 62932 KB Output is correct
21 Incorrect 31 ms 62924 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1575 ms 90328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 62932 KB Output is correct
2 Correct 29 ms 62844 KB Output is correct
3 Correct 26 ms 62932 KB Output is correct
4 Correct 27 ms 63052 KB Output is correct
5 Correct 26 ms 62872 KB Output is correct
6 Correct 25 ms 62808 KB Output is correct
7 Correct 27 ms 62948 KB Output is correct
8 Correct 29 ms 62936 KB Output is correct
9 Correct 28 ms 62884 KB Output is correct
10 Correct 25 ms 62948 KB Output is correct
11 Correct 27 ms 62860 KB Output is correct
12 Correct 26 ms 62932 KB Output is correct
13 Correct 26 ms 62952 KB Output is correct
14 Correct 25 ms 62932 KB Output is correct
15 Correct 26 ms 62856 KB Output is correct
16 Correct 25 ms 62932 KB Output is correct
17 Correct 24 ms 62932 KB Output is correct
18 Correct 24 ms 62876 KB Output is correct
19 Correct 28 ms 62828 KB Output is correct
20 Correct 34 ms 62800 KB Output is correct
21 Incorrect 26 ms 62828 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 62932 KB Output is correct
2 Correct 25 ms 62924 KB Output is correct
3 Correct 26 ms 62836 KB Output is correct
4 Correct 32 ms 62848 KB Output is correct
5 Correct 29 ms 62924 KB Output is correct
6 Correct 28 ms 62848 KB Output is correct
7 Correct 26 ms 62936 KB Output is correct
8 Correct 26 ms 62872 KB Output is correct
9 Correct 25 ms 62824 KB Output is correct
10 Correct 25 ms 62932 KB Output is correct
11 Correct 29 ms 62860 KB Output is correct
12 Correct 32 ms 62928 KB Output is correct
13 Correct 27 ms 62816 KB Output is correct
14 Correct 27 ms 62900 KB Output is correct
15 Correct 26 ms 62952 KB Output is correct
16 Correct 28 ms 62928 KB Output is correct
17 Correct 26 ms 62928 KB Output is correct
18 Correct 31 ms 62828 KB Output is correct
19 Correct 28 ms 62936 KB Output is correct
20 Correct 27 ms 62932 KB Output is correct
21 Incorrect 26 ms 62932 KB Output isn't correct
22 Halted 0 ms 0 KB -