제출 #1288351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288351		nanaseyuzuki	서열 (APIO23_sequence)	C++20	100 / 100	782 ms	81052 KiB

sequence

#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int,int>
#define all(a) a.begin(), a.end()
// #define int long long
using namespace std;

const int mn = 5e5 + 5;
const int mod = 1000000007LL, inf = 2e18;

struct SegTree{
    pii st[mn << 2];
    int lz[mn << 2];

    pii merge(pii a, pii b){
        return {min(a.fi, b.fi), max(a.se, b.se)};
    }

    void build(int id, int l, int r){
		if(l == r){
			st[id] = {-l, -l};
			return;
		}
		int m = (l + r) >> 1;
		build(id << 1, l, m);
		build(id << 1 | 1, m + 1, r);
		st[id] = merge(st[id << 1], st[id << 1 | 1]);
	}

    void down(int id){
        if(!lz[id]) return;
        st[id << 1].fi += lz[id], st[id << 1].se += lz[id];
        lz[id << 1] += lz[id];
        st[id << 1 | 1].fi += lz[id], st[id << 1 | 1].se += lz[id];
        lz[id << 1 | 1] += lz[id];
        lz[id] = 0;
    }

    void update(int id, int l, int r, int u, int v, int val){
        if(l > v || r < u) return;
        if(l >= u && r <= v){
            st[id].fi += val, st[id].se += val;
            lz[id] += val;
            return;
        }
        down(id);
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);
        st[id] = merge(st[id << 1], st[id << 1 | 1]);
    }
    
    pii get(int id, int l, int r, int u, int v){
        if(l > v || r < u) return {inf, - inf};
        if(l >= u && r <= v) return st[id];
        down(id);
        int mid = (l + r) >> 1;
        return merge(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }
} pre, suf;

int n, a[mn], min_val[2][mn], max_val[2][mn];
vector <int> pos[mn];

bool check(int mid){
    for(int i = 1; i <= n; i++){
        if(pos[i].size() < mid) continue;
        for(int j = 0; j < pos[i].size() - mid + 1; j++){
            int l = pos[i][j], r = pos[i][j + mid - 1];
            if(min_val[1][r] - max_val[0][l] <= 0 && max_val[1][r] - min_val[0][l] >= 0) return true;
        }
    }
    return false;
}

int sequence(int N, vector<int> A){

    n = N;

    for(int i = 1; i <= n; i++){
        a[i] = A[i - 1];
        pos[a[i]].push_back(i);
    }
    
    pre.build(1, 0, n); suf.build(1, 0, n);

    for(int i = 1; i <= n; i++){
        for(auto p : pos[i]) suf.update(1, 0, n, p, n, 2);

        for(auto p : pos[i]){
            min_val[0][p] = suf.get(1, 0, n, 0, p - 1).fi, max_val[0][p] = pre.get(1, 0, n, 0, p - 1).se;
            min_val[1][p] = pre.get(1, 0, n, p, n).fi, max_val[1][p] = suf.get(1, 0, n, p, n).se;
        }

        for(auto p : pos[i]) pre.update(1, 0, n, p, n, 2);
    }

    int l = 1, r = n, ans = -1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(check(mid)){
            l = mid + 1;
            ans = mid;
        }
        else r = mid - 1;
    }
    return ans;
}

// void solve(){
//     int N; cin >> N;
//     vector <int> A(N);
//     for(int i = 0; i < N; i++) cin >> A[i];
//     cout << sequence(N, A);
// }
// // Waifu of the day: Kagari Fuyukawa
// signed main(){
//     ios::sync_with_stdio(false);
//     cin.tie(NULL);
//     cout.tie(NULL);
//     if(fopen("mario.inp", "r")){
//         freopen("mario.inp", "r", stdin);
//         freopen("mario.out", "w", stdout);
//     }
//     int t = 1;
//     // cin >> t;
//     while(t--) solve();
// }

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp:11:37: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
   11 | const int mod = 1000000007LL, inf = 2e18;
      |                                     ^~~~

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 7 / 7
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 22 / 22
• Subtask 7: 18 / 18