結果

問題 No.2697 Range LIS Query
ユーザー GGanariGGanari
提出日時 2024-03-22 23:24:10
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 270 ms / 10,000 ms
コード長 4,410 bytes
コンパイル時間 4,376 ms
コンパイル使用メモリ 264,124 KB
実行使用メモリ 37,668 KB
最終ジャッジ日時 2024-09-30 12:42:30
合計ジャッジ時間 7,846 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 7 ms
6,816 KB
testcase_04 AC 8 ms
6,820 KB
testcase_05 AC 7 ms
6,820 KB
testcase_06 AC 236 ms
37,596 KB
testcase_07 AC 232 ms
37,620 KB
testcase_08 AC 232 ms
37,668 KB
testcase_09 AC 146 ms
37,632 KB
testcase_10 AC 140 ms
37,504 KB
testcase_11 AC 140 ms
37,596 KB
testcase_12 AC 143 ms
33,012 KB
testcase_13 AC 153 ms
26,328 KB
testcase_14 AC 212 ms
27,136 KB
testcase_15 AC 270 ms
37,600 KB
testcase_16 AC 267 ms
37,632 KB
testcase_17 AC 260 ms
37,632 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
#define INF 1000000001LL
#define LNF 1000000000000000001LL
#define MOD 998244353LL
#define MAX 2001
#define long long long
#define all(x) x.begin(),x.end()
using namespace std;

struct Node
{
    int value[4][4] = {{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};
};
class SegTree
{
private:
    vector<Node> arr;
    vector<Node> tree;
    vector<int> lazy;
    int n;
    Node trash; //의미없는 값 입력
    Node merge(Node a, Node b)
    {
        //여기를 커스텀 구현
        Node res;
        for(int i = 0; i<4; i++)
        {
            for(int j = i; j<4; j++)
            {
                for(int k=i;k<=j; k++)
                {
                    res.value[i][j] = max(res.value[i][j],a.value[i][k]+b.value[k][j]);
                }
            }
        }
        return res;
    }

    void lazyUpdate(int node, int start, int end)
    {
        if(lazy[node] == -1)
            return;
        for(int x = 0; x<4; x++)
        {
            for(int y = x; y<4; y++)
            {
                if(x <= lazy[node] && y >= lazy[node])
                    tree[node].value[x][y] = end-start+1;
                else
                    tree[node].value[x][y] = 0;
            }
        }
        if(start != end)
        {
        lazy[node*2] = lazy[node];
        lazy[node*2+1] = lazy[node];
        }
        lazy[node] = -1;
    }
    Node init(int node, int start, int end)
    {
        if(start == end)
            return tree[node] = arr[start];
        int mid = (start+end)/2;
        return tree[node] = merge(init(node*2,start,mid),init(node*2+1,mid+1,end));
    }
    Node query(int node, int start, int end, int left, int right)
    {
        lazyUpdate(node,start,end);
        if(start > right || end < left)
            return trash;
        if(start >= left && end <= right)
            return tree[node];
        int mid = (start+end)/2;
        return merge(query(node*2,start,mid,left,right),query(node*2+1,mid+1,end,left,right));
    }
    Node update(int node, int start, int end, int left, int right, long l)
    {
        lazyUpdate(node,start,end);
        if(start > right || end < left)
            return tree[node];
        if(start >= left && end <= right)
        {
            lazy[node] = l;
            lazyUpdate(node,start,end);
            return tree[node];
        }
        int mid = (start+end)/2;
        return tree[node]=merge(update(node*2,start,mid,left,right,l),update(node*2+1,mid+1,end,left,right,l));
    }
public:
    void init(int l)
    {
        n = l;
        arr = vector<Node>(n);
        tree = vector<Node>(4*n);
    }
    void init(vector<Node> a)
    {
        n = a.size();
        arr = a;
        tree = vector<Node>(4*n);
        init(1,0,n-1);
    }
    void init(vector<long> a)
    {
        n = a.size();
        arr = vector<Node>(n);
        for(int i = 0; i<n; i++)
        {
            for(int x = 0; x<4; x++)
            {
                for(int y = x; y<4; y++)
                {
                    if(x <= a[i] && y >= a[i])
                        arr[i].value[x][y] = 1;
                }
            }
        }
        tree = vector<Node>(4*n);
        lazy = vector<int>(4*n,-1);
        init(1,0,n-1);
    }
    long query(int left, int right)
    {
        if(left > right)
            swap(left,right);
        // for(int x = 0; x<4; x++)
        // {
        //     for(int y = 0; y<4; y++)
        //     {
        //         cout << query(1,0,n-1,left,right).value[x][y] << " ";
        //     }
        //     cout << "\n";
        // }
        return query(1,0,n-1,left,right).value[0][3];
    }
    void update(int left,int right, long val)
    {
        update(1,0,n-1,left,right,val);
    }
};
int main()
{
	ios_base::sync_with_stdio(0); 
    cin.tie(0);

    int n;
    cin >> n;

    vector<long> arr(n);

    for(int i = 0; i<n; i++)
    {
        cin >> arr[i];
        arr[i]--;
    }

    SegTree seg;
    seg.init(arr);

    int q;
    cin >> q;

    while(q--)
    {
        int t,l,r;
        cin >> t >> l >> r;
        l--;
        r--;
        if(t == 1)
            cout << seg.query(l,r) << "\n";
        else
        {
            int x;
            cin >> x;
            seg.update(l,r,x-1);
        }
    }

    return 0;
}
0