Submission #1099090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099090		Fallout3691	Snowball (JOI21_ho_t2)	C++17	100 / 100	2364 ms	21696 KiB

Main

#pragma once
#pragma GCC optimize("Ofast, no-stack-protector, unroll-loops, fast-math, 03")
#pragma GCC optimization("03, unroll-loops")
// #pragma GCC target("avx, avx2, fma, bmi, bmi2, popcnt, lzcnt")
// #pragma GCC target("sse, sse2, sse3, ssse3, sse4.1, sse4.2, tune=native")

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main() {
    int n, q;
    cin >> n >> q;

    vector<int> a(n + 2);
    a[0] = -1e18, a[n + 1] = 1e18;
    for (int i = 1; i <= n; i++)
        cin >> a[i];


    int mn = 0, mx = 0;
    int cur = 0;
    int x;
    map<int, int> mp;
    mp[0] = 0;
    for (int i = 1; i <= q; i++) {
        cin >> x;
        cur += x;
        if (cur < mn) {
            mp[cur] = i;
            mn = cur;
        }
        if (cur > mx) {
            mp[cur] = i;
            mx = cur;
        }
    }

    for (int i = 1; i <= n; i++) {
        int left = a[i], right = a[i];
        {
            int l = a[i - 1], r = a[i];
            while (r - l > 1) {
                int mid = (l + r) / 2;
                int x = mid - a[i];
                int y = mid - a[i - 1];
                auto it1 = mp.upper_bound(x);
                if (it1 == mp.begin()) {
                    l = mid;
                    continue;
                }
                --it1;
                auto it2 = mp.lower_bound(y);
                if (it2 == mp.end()) {
                    r = mid;
                    continue;
                }
                if ((it1 -> second) < (it2 -> second))
                    r = mid;
                else
                    l = mid;
            }
            auto it1 = mp.upper_bound(r - 1 - a[i]);
            auto it2 = mp.lower_bound(r - a[i - 1]);
            if ((it1 != mp.begin()) && ((it2 == mp.end()) ||((--it1) -> second < it2 -> second)))
                r--;
            left = r;
        }
        {
            int l = a[i], r = a[i + 1];
            while (r - l > 1) {
                int mid = (l + r) / 2;
                int x = mid - a[i];
                int y = mid - a[i + 1];
                auto it1 = mp.lower_bound(x);
                if (it1 == mp.end()) {
                    r = mid;
                    continue;
                }
                auto it2 = mp.upper_bound(y);
                if (it2 == mp.begin()) {
                    l = mid;
                    continue;
                }
                --it2;
                if ((it1 -> second) < (it2 -> second))
                    l = mid;
                else
                    r = mid;
            }
            auto it1 = mp.lower_bound(l + 1 - a[i]);
            auto it2 = mp.upper_bound(l - a[i + 1]);
            if ((it1 != mp.end()) && ((it2 == mp.begin() || (it1 -> second < (--it2) -> second))))
                l++;
            right = l;
        }
        cout << right - left << endl;
    }

    return 0;
}

Compilation message (stderr)

Main.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
Main.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization("03, unroll-loops")
      | 
Main.cpp:2:78: warning: bad option '-f no-stack-protector' to pragma 'optimize' [-Wpragmas]
    2 | #pragma GCC optimize("Ofast, no-stack-protector, unroll-loops, fast-math, 03")
      |                                                                              ^
Main.cpp:2:78: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
Main.cpp:2:78: warning: bad option '-f fast-math' to pragma 'optimize' [-Wpragmas]
Main.cpp:2:78: warning: bad option '-f 03' to pragma 'optimize' [-Wpragmas]
Main.cpp:12:13: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   12 | signed main() {
      |             ^
Main.cpp:12:13: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:12:13: warning: bad option '-f fast-math' to attribute 'optimize' [-Wattributes]
Main.cpp:12:13: warning: bad option '-f 03' to attribute 'optimize' [-Wattributes]

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67