제출 #1181814

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181814		cpdreamer	서열 (APIO23_sequence)	C++20	11 / 100	2095 ms	16452 KiB

sequence

#include "sequence.h"

#include <vector>

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair
#define F first
#define all(v) v.begin(),v.end()
#define V vector
#define pb push_back
#define S second
const ll MOD=(ll)1e9+7;
void file() {
    freopen("input.txt.txt", "r", stdin);
    freopen("output.txt.txt", "w", stdout);
}
struct segtree {
private:
    struct node {
        ll sum;
    };
    node neutral = {0};

    node single(int x) {
        return {x};
    }

    node merge(node a, node b) {
        return {a.sum + b.sum};
    };
public:
    int size;
    V<node> query;

    void init(int n) {
        size = 1;
        while (size < n)size *= 2;
        query.assign(2 * size, neutral);
    }

    void build(V<int> &a, int x, int lx, int rx) {
        if (rx - lx == 1) {
            if (lx < a.size())
                query[x] = single(a[lx]);
            return;
        }
        int m = (lx + rx) / 2;
        build(a, 2 * x + 1, lx, m);
        build(a, 2 * x + 2, m, rx);
        query[x] = merge(query[2 * x + 1], query[2 * x + 2]);
    }

    void build(V<int> a) {
        build(a, 0, 0, size);
    }

    void set(int i, int v, int x, int lx, int rx) {
        if (rx - lx == 1) {
            query[x] = single(v);
            return;
        }
        int m = (lx + rx) / 2;
        if (i < m) {
            set(i, v, 2 * x + 1, lx, m);
        } else
            set(i, v, 2 * x + 2, m, rx);
        query[x] = merge(query[2 * x + 1], query[2 * x + 2]);
    }

    void set(int i, int v) {
        set(i, v, 0, 0, size);
    }

    node calc(int l, int r, int x, int lx, int rx) {
        if (l <= lx && rx <= r)
            return query[x];
        if (lx >= r || rx <= l)
            return neutral;
        int m = (lx + rx) / 2;
        node a = calc(l, r, 2 * x + 1, lx, m);
        node b = calc(l, r, 2 * x + 2, m, rx);
        return merge(a, b);
    }

    ll calc(int l, int r) {
        return calc(l, r, 0, 0, size).sum;
    }
};
int sequence(int N, std::vector<int> A) {
    int ans = 0;
    segtree tree;
    for (int i = 0; i < N; i++) {
        tree.init(N + 1);
        V<int> occ(N + 1, 0);
        tree.build(occ);
        for (int j = i; j < N; j++) {
            int d = j - i + 1;
            occ[A[j]]++;
            tree.set(A[j], occ[A[j]]);
            int md1 = -1, md2 = -1;
            int l = 1, r = N;
            while (l <= r) {
                int m = l + (r - l) / 2;
                if (tree.calc(1, m + 1) >= (d + 1) / 2) {
                    md1 = m;
                    r = m - 1;
                } else
                    l = m + 1;
            }
            l = 1, r = N;
            while (l <= r) {
                int m = l + (r - l) / 2;
                if (tree.calc(1, m + 1) >= (d + 2) / 2) {
                    md2 = m;
                    r = m - 1;
                } else
                    l = m + 1;
            }
            ans = max(ans, max(occ[md1], occ[md2]));
        }
    }
    return ans;
}

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

sequence.cpp: In function 'void file()':
sequence.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen("input.txt.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen("output.txt.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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