Submission #319205

#	Time	Username	Problem	Language	Result	Execution time	Memory
319205		mohamedsobhi777	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	12 / 100	18 ms	2664 KiB

worst_reporter3

#include <bits/stdc++.h>

#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

#define I inline void
#define S struct
#define vi vector<int>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;
using ll = long long;
using ld = long double;

const int N = 2e5 + 7, mod = 1e9 + 7;
const ll inf = 2e18;

// How interesting!

int n, m;
int a[N], ans[N];
vector<pair<pii, pii>> v;
vector<int> p = {0};

int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        //freopen("in.in", "r", stdin);
        cin >> n >> m;
        for (int i = 0; i < n; ++i)
        {
                cin >> a[i];
                p.push_back(-(i + 1));
        }
        reverse(a, a + n);
        a[n] = 1;

        for (int i = 0; i < m; ++i)
        {
                int x, y, z;
                cin >> x >> y >> z;
                v.push_back({{x, i}, {y, z}});
        }
        sort(v.begin(), v.end());
        sort(p.begin(), p.end());
        int k = 0;
        for (int i = 0; i <= v.back().first.first; ++i)
        {
                for (int j = n; ~j; --j)
                {
                        if (j < n)
                        {
                                if (p[j + 1] - p[j] > a[j])
                                {
                                        p[j] = p[j + 1] - 1;
                                }
                                else
                                        break;
                        }
                        else
                        {
                                p[j]++;
                        }
                }
                while (k < m && v[k].first.first == i + 1)
                {
                        ans[v[k].first.second] = upper_bound(p.begin(), p.end(), v[k].second.second) - lower_bound(p.begin(), p.end(), v[k].second.first);
                        ++k;
                }
        }

        for (int i = 0; i < m; ++i)
                cout << ans[i] << "\n";
        return 0;
}

/*
        - bounds sir (segtree = 4N, eulerTour = 2N, ...)
        - a variable defined twice?
        - will overflow?
        - is it a good complexity?
        - don't mess up indices (0-indexed vs 1-indexed)
        - reset everything between testcases. 
*/

• Subtask 1: 0 / 7
• Subtask 2: 12 / 12
• Subtask 3: 0 / 81