oj.uz

Submission #202670

# Submission time Handle Problem Language Result Execution time Memory
202670 2020-02-17T17:11:48 Z ismagilov Fire (JOI20_ho_t5) C++14
20 / 100
 1000 ms 124724 KB 
/**
 * 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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 380 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 6 ms 376 KB Output is correct
19 Correct 6 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 6 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 380 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Correct 6 ms 376 KB Output is correct
28 Correct 6 ms 504 KB Output is correct
29 Correct 5 ms 508 KB Output is correct
30 Correct 11 ms 376 KB Output is correct
31 Correct 5 ms 376 KB Output is correct
32 Correct 5 ms 376 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 650 ms 113876 KB Output is correct
3 Correct 692 ms 113672 KB Output is correct
4 Correct 636 ms 115276 KB Output is correct
5 Correct 611 ms 117720 KB Output is correct
6 Correct 752 ms 121120 KB Output is correct
7 Correct 605 ms 116056 KB Output is correct
8 Correct 723 ms 124724 KB Output is correct
9 Correct 637 ms 116952 KB Output is correct
10 Correct 608 ms 112940 KB Output is correct
11 Correct 668 ms 124300 KB Output is correct
12 Correct 618 ms 115136 KB Output is correct
13 Correct 617 ms 116484 KB Output is correct
14 Correct 669 ms 119348 KB Output is correct
15 Correct 631 ms 113552 KB Output is correct
16 Correct 698 ms 117472 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 727 ms 116060 KB Output is correct
3 Correct 800 ms 116592 KB Output is correct
4 Correct 951 ms 122980 KB Output is correct
5 Correct 719 ms 118616 KB Output is correct
6 Correct 747 ms 118248 KB Output is correct
7 Correct 757 ms 122788 KB Output is correct
8 Correct 878 ms 120024 KB Output is correct
9 Correct 724 ms 116884 KB Output is correct
10 Correct 740 ms 121492 KB Output is correct
11 Correct 756 ms 122676 KB Output is correct
12 Correct 793 ms 119956 KB Output is correct
13 Correct 789 ms 116812 KB Output is correct
14 Correct 741 ms 114640 KB Output is correct
15 Correct 862 ms 120400 KB Output is correct
16 Correct 722 ms 116372 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 69832 KB Output is correct
2 Correct 428 ms 70344 KB Output is correct
3 Correct 452 ms 72008 KB Output is correct
4 Correct 448 ms 70216 KB Output is correct
5 Correct 486 ms 70600 KB Output is correct
6 Correct 448 ms 70572 KB Output is correct
7 Correct 477 ms 71752 KB Output is correct
8 Correct 447 ms 71124 KB Output is correct
9 Correct 610 ms 71080 KB Output is correct
10 Correct 460 ms 71112 KB Output is correct
11 Correct 495 ms 71220 KB Output is correct
12 Correct 438 ms 70756 KB Output is correct
13 Correct 444 ms 70344 KB Output is correct
14 Correct 428 ms 70856 KB Output is correct

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 380 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 6 ms 376 KB Output is correct
19 Correct 6 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 6 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 380 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Correct 6 ms 376 KB Output is correct
28 Correct 6 ms 504 KB Output is correct
29 Correct 5 ms 508 KB Output is correct
30 Correct 11 ms 376 KB Output is correct
31 Correct 5 ms 376 KB Output is correct
32 Correct 5 ms 376 KB Output is correct
33 Correct 736 ms 118336 KB Output is correct
34 Correct 754 ms 123200 KB Output is correct
35 Execution timed out 1029 ms 121488 KB Time limit exceeded
36 Halted 0 ms 0 KB -