Submission #202669

#	Time	Username	Problem	Language	Result	Execution time	Memory
202669		ismagilov	Fire (JOI20_ho_t5)	C++14	1 / 100	1114 ms	262148 KiB

ho_t5

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Azat Ismagilov
 */

                                         /*..         ....
                                    ..',,'..............''...'''.','..
                                  .';'..                          ..',,'.
                                 .'..                                 .';,.
                                .'.              .:ol;.                 .';.
                                ..              .cO00k:.                  .,.
                               ..          .'...;k00Od'                   .'.
                              ...        .;xOkxdk00Od,                    ...
                             ...        .,x0000000Od;.                     ..
                             .'         .cO00OOOOOOd;'...                 ...
                            .'.          .;lxkOOOO00Okkxo:.               .'.
                           .'.             .cxOOOOO000000Ol.              .'.
                          .'.             .ck00OOd::oxOOOOl.              .,.
                          ''...,;''''''''':kKK0Od,. ..:xOo'               .,.
                         ';,;;;:,..........;lxOx:.    .';'               .''
                        'cc;..               .,;:,..                     ...
                       ,oc.       ..........    .',:;,..                 ...
                      'o:.     .,;;;,,,,;;;;;'.    ..,;;,..              ...
                      ';.      ...         .,::.       .,::'.            .'.
                      ..                     .',.        ..;;'.         ...
                     ..          .',,;;,'.                  ':;'.       .,.
                    .,::;,.        .......                   .';:'.    .,,.
                    .;dOK0x;.                         .        .':;.   .,.
                    ...,cdxdl;.              ..,;;;cloddoc;.     .,:,. .,.
                   .     ...;cl:.          ':ldxxdocccclol;.      ..:;.',.
                   .   .;llc;',c;.       .,:,''';::;'.  ..          .;:;'
                      .:xdoxko,',.      .,:. .;llc:ldl.              .;c.
                      .lxdoxkd:''.     .;:.  .cxl'';od;.          .. .,,
                      .:clool;.',.     .:'   .:dxolccl;.         .::;,:'
                       .;::,.. .,.     .;.   .,:;:;,,;'         .,;,:ol.
                         ..    ',.     .;.    .',,,,,.          .,:llc;.
                              .,'      .,.                      .;lxxc'
                             .,;.      .;.                      .;lxxc.
            ..              .;;.       .:'                      .;cc,.
           ...';'          .;;.        .;:.                      ,:'
          .;c:;.       .. .,;.       ....,;.                     .'.
         .,lc,.      .':,..,:,''....;c:;'':'..              ..   .'.
         .;:;.      .,:'   .::,,;;;;;..',;,..,,.            .,.  .'.
        .'',,.     .,;.                      .;,            .'.  ...
        .'',,.    .,;.                        ';.           .,.  .'.
        .'...     .;.                         .,,.          .,'   ..
        .'.      .;,.                          .::.         .,'   .
        .'.     .,;.                            ,c'         .,'  .'.
        .'.     .:'                             .,'          .. .,'
         ''.    ,;.    .....................    .;'            .:,
         .,.   .,;.   ..'''''''''''''''''','.  .,;.           .::.
          .,.   ,;.                           .,;.           .;,.
          .,,.  .:,.                         .;;.          .''.
           .,'   .'.                         ...          .,.
            .''                                          .,.
             .,'.                                       .'.
              .'.                                      .*/

#include <fstream>

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
#include <set>
#include <map>

#define int long long
#define ld long double
#define fs first
#define sc second
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define eb emplace_back
#define mp make_pair
#define len(v) ((int)v.size())
#define vc vector
#define pr pair
#define all(v) v.begin(), v.end()
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize("unroll-loops")

using namespace std;

template<typename T, typename U>
inline ostream &operator<<(ostream &_out, const pair<T, U> &_p) {
    _out << _p.first << ' ' << _p.second;
    return _out;
}

template<typename T, typename U>
inline istream &operator>>(istream &_in, pair<T, U> &_p) {
    _in >> _p.first >> _p.second;
    return _in;
}

template<typename T>
inline ostream &operator<<(ostream &_out, const vector<T> &_v) {
    if (_v.empty()) { return _out; }
    _out << _v.front();
    for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) { _out << ' ' << *_it; }
    return _out;
}

template<typename T>
inline istream &operator>>(istream &_in, vector<T> &_v) {
    for (auto &_i : _v) { _in >> _i; }
    return _in;
}

const int MAXN = 6e5;
const int INF = 1e9;
const int MOD = 1e9 + 7;

vc<pr<pr<int, int>, pr<int, int>>> lefts, rights;


void add_segment(int l1, int r1, int l2, int r2, int value) {
    //cout << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << ' ' << value << endl;
    if (r1 - l1 >= r2 - l2) {
        for (int i = l1; i <= r1; i++) {
            lefts.pb({{i,      value},
                      {l2 - i, r2 - i}});
        }
    } else {
        for (int i = l2; i <= r2; i++) {
            rights.pb({{i,      value},
                       {i - r1, i - l1}});
        }
    }
}

int n;
int t[MAXN];

void init(int nn) {
    n = nn;
    fill(t, t + n, 0);
}

void upd(int v, int x) {
    for (; v < n; v = (v | (v + 1))) {
        t[v] += x;
    }
}

int get(int v) {
    int ans = 0;
    for (; v >= 0; v = (v & (v + 1)) - 1) {
        ans += t[v];
    }
    return ans;
}

int get(int l, int r) {
    return get(r) - get(l - 1);
}

class pozhar {
public:
    void solve(std::istream &in, std::ostream &out) {
        int n, q;
        in >> n >> q;
        vc<int> s(n);
        in >> s;
        set<int> limiters;
        limiters.insert(-1);
        limiters.insert(n);
        vc<pr<int, int>> dds;
        for (int i = 0; i < n; i++) {
            dds.pb({s[i], i});
        }
        sort(all(dds));
        reverse(all(dds));
        for (auto v : dds) {
            auto r = (*limiters.lower_bound(v.sc)) - 1;
            auto l = (*prev(limiters.lower_bound(v.sc))) + 1;
            if (l <= v.sc && v.sc <= r) {
                add_segment(l, v.sc, v.sc, r, v.fs);
            }
            limiters.insert(v.sc);
        }
        /*
        cout << "lefts\n";
        for (auto v : lefts) {
            cout << v << endl;
        }
        cout << "rights\n";
        for (auto v : rights) {
            cout << v << endl;
        }
         */
        vc<int> ans(q);
        vc<pr<int, pr<int, int>>> que(q);
        vc<vc<int>> bylen(n + 2);
        int i = 0;
        for (auto &v : que) {
            in >> v.fs >> v.sc;
            v.sc.fs--, v.sc.sc--;
            bylen[v.fs].pb(i);
            i++;
        }
        {
            int maxi = 0;
            for (int i = 0; i < n; i++) {
                maxi = max(maxi, s[i]);
                rights.pb({{i,     maxi},
                           {i + 1, n}});
            }
        }
        {
            vc<vc<pr<int, int>>> gr(n + 2);
            for (auto v : lefts) {
                gr[v.sc.fs].pb(v.fs);
                v.fs.sc *= -1;
                gr[v.sc.sc + 1].pb(v.fs);
            }
            init(2 * n);
            for (int i = 0; i <= n; i++) {
                for (auto d : gr[i]) {
                    upd(d.fs + n, d.sc);
                }
                for (auto d : bylen[i]) {
                    ans[d] += get(que[d].sc.fs - i + n, que[d].sc.sc - i + n);
                }
            }
        }
        {
            vc<vc<pr<int, int>>> gr(n + 2);
            for (auto v : rights) {
                gr[v.sc.fs].pb(v.fs);
                v.fs.sc *= -1;
                gr[v.sc.sc + 1].pb(v.fs);
            }
            init(2 * n);
            for (int i = 0; i <= n; i++) {
                for (auto d : gr[i]) {
                    upd(d.fs, d.sc);
                }
                for (auto d : bylen[i]) {
                    ans[d] += get(que[d].sc.fs, que[d].sc.sc);
                }
            }
        }
        for (auto v : ans) {
            out << v << '\n';
        }
    }
};


signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	pozhar solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 80