Submission #437753

#	Time	Username	Problem	Language	Result	Execution time	Memory
437753		kiennguyen246	Progression (NOI20_progression)	C++14	24 / 100	199 ms	9404 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;
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];

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";

            }
        }
    }
}

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();
//    Sub1::Main();
    cerr << "\n\n-----------------\n";
    return 0;
}

Compilation message (stderr)

Progression.cpp: In function 'int main()':
Progression.cpp:113:10: warning: variable 'no_change' set but not used [-Wunused-but-set-variable]
  113 |     bool no_change = 1;
      |          ^~~~~~~~~
Progression.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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