제출 #437875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
437875		kiennguyen246	Progression (NOI20_progression)	C++14	59 / 100	326 ms	22648 KiB

Progression

/**
 * \author Nguyen Duc Kien
 * \date 20/06/2021
 */

///Task name
#define TASK ""

///-------------------------------------------///

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e5 + 5;

int n, Q, f[maxn], g[maxn], ftree[maxn << 2], lftree[maxn << 2];
long long a[maxn];
struct query
{
    int req, L, R, S, C;

    void inp()
    {
        cin >> req >> L >> R;
        if (req != 3) cin >> S >> C;
    }

}q[maxn];

void LazyUpd(int nod)
{
    lftree[nod * 2] = lftree[nod * 2 + 1] = lftree[nod];
    ftree[nod * 2] = max(ftree[nod * 2], lftree[nod * 2]);
    ftree[nod * 2 + 1] = max(ftree[nod * 2 + 1], lftree[nod * 2 + 1]);
    lftree[nod] = 0;
}

void Init(int nod, int l, int r)
{
    if (l == r)
    {
        ftree[nod] = f[l];
        return;
    }

    int mid = (l + r) / 2;
    Init(nod * 2, l, mid);
    Init(nod * 2 + 1, mid + 1, r);
    ftree[nod] = max(ftree[nod * 2], ftree[nod * 2 + 1]);
}

void Upd(int nod, int l, int r, int u, int v, int w)
{
    if (l > v || r < u) return;
    if (l >= u && r <= v)
    {
        ftree[nod] = w;
        lftree[nod] = w;
        return;
    }

    if (lftree[nod]) LazyUpd(nod);
    int mid = (l + r) / 2;
    Upd(nod * 2, l, mid, u, v, w);
    Upd(nod * 2 + 1, mid + 1, r, u, v, w);
    ftree[nod] = max(ftree[nod * 2], ftree[nod * 2 + 1]);
}

int Max(int nod, int l, int r, int u, int v)
{
    if (l > v || r < u) return 0;
    if (l >= u && r <= v) return ftree[nod];

    if (lftree[nod]) LazyUpd(nod);
    int mid = (l + r) / 2;
    int L = Max(nod * 2, l, mid, u, v);
    int R = Max(nod * 2 + 1, mid + 1, r, u, v);
    return max(L, R);
}

///Shortcuts
void Upd(int u, int v, int w) {Upd(1, 1, n, u, v, w);}
int Max(int u, int v) {return Max(1, 1, n, u, v);}

namespace Sub1
{
    void Main()
    {
        int res = 1;
        int d = 2;
        a[n + 1] = 1e9 + 69;
        for (int i = 2; i <= n; i ++)
        {
            if (a[i + 1] - a[i] == a[i] - a[i - 1]) d ++;
            else res = max(res, d), d = 2;
        }
        bool f2 = 0;
        for (int i = 1; i <= Q; i ++)
        {
            if (q[i].req == 2) f2 = 1;
            else if (q[i].req == 3)
            {
                if (f2 == 0) cout << res << "\n";
                else cout << n << "\n";
            }
        }
    }
}

namespace Sub2
{
    void Main()
    {
        for (int t = 1; t <= Q; t ++)
        {
            int L = q[t].L;
            int R = q[t].R;
            int S = q[t].S;
            int C = q[t].C;
            if (q[t].req == 1)
            {
                for (int i = L; i <= R; i ++)
                    a[i] = a[i] + S + 1ll * (i - L) * C;
            }
            else if (q[t].req == 2)
            {
                for (int i = L; i <= R; i ++)
                    a[i] = S + 1ll * (i - L) * C;
            }
            else
            {
                int res = 1, cur = 2;
                long long d = a[L + 1] - a[L];
                for (int i = L + 1; i < R; i ++)
                {
                    if (a[i + 1] - a[i] == d) cur ++;
                    else
                    {
                        res = max(res, cur);
                        cur = 2;
                        d = a[i + 1] - a[i];
                    }
                }
                res = max(res, cur);
                if (L == R) res = 1;
                cout << res << "\n";

            }
        }
    }
}

namespace Sub3
{
    void Main()
    {
        g[1] = 1;
        g[2] = 2;
        for (int i = 2; i < n; i ++)
        {
            if (a[i + 1] - a[i] == a[i] - a[i - 1]) g[i + 1] = g[i] + 1;
            else g[i + 1] = 2;
        }
        f[n] = 1;
        f[n - 1] = 2;
        for (int i = n - 1; i > 1; i --)
        {
            if (a[i - 1] - a[i] == a[i] - a[i + 1]) f[i - 1] = f[i] + 1;
            else f[i - 1] = 2;
        }
        Init(1, 1, n);
        for (int t = 1; t <= Q; t ++)
        {
            int L = q[t].L;
            int R = q[t].R;
            int res = min(R - L + 1, max(f[L], g[R]));
            int l = L + f[L];
            int r = R - g[R];
            if (l <= r) res  = max(res, Max(l, r));
            if (l - 1 != r + 1)
            {
                res = max(res, f[l - 1]);
                res = max(res, g[r + 1]);
            }
            res = min(res, R - L + 1);
            cout << res << "\n";
        }
    }


}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cerr << "Processing...\n\n";
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
//        freopen(TASK".OUT", "w", stdout);
    }

    cin >> n >> Q;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    bool all_1_n = 1;
    bool no_change = 1;
    for (int i = 1; i <= Q; i ++)
    {
        q[i].inp();
        if (q[i].L != 1 || q[i].R != n) all_1_n = 0;
        if (q[i].req != 3) no_change = 0;
    }
    if (n <= 1000 && Q <= 1000) Sub2::Main();
    else if (all_1_n) Sub1::Main();
    else if (no_change) Sub3::Main();
//    Sub3::Main();
    cerr << "\n\n-----------------\n";
    return 0;
}

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

Progression.cpp: In function 'int main()':
Progression.cpp:201:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 0 / 11
• Subtask 5: 0 / 13
• Subtask 6: 0 / 17