oj.uz

답안 #202669

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
202669 2020-02-17T17:10:38 Z ismagilov Fire (JOI20_ho_t5) C++14
1 / 100
 1000 ms 262148 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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 5 ms 504 KB Output is correct
12 Correct 5 ms 504 KB Output is correct
13 Correct 5 ms 504 KB Output is correct
14 Correct 5 ms 500 KB Output is correct
15 Correct 5 ms 504 KB Output is correct
16 Correct 5 ms 504 KB Output is correct
17 Correct 5 ms 504 KB Output is correct
18 Correct 5 ms 504 KB Output is correct
19 Correct 5 ms 504 KB Output is correct
20 Correct 5 ms 504 KB Output is correct
21 Correct 5 ms 504 KB Output is correct
22 Correct 5 ms 504 KB Output is correct
23 Correct 5 ms 504 KB Output is correct
24 Correct 5 ms 504 KB Output is correct
25 Correct 5 ms 504 KB Output is correct
26 Correct 6 ms 504 KB Output is correct
27 Correct 6 ms 504 KB Output is correct
28 Correct 5 ms 504 KB Output is correct
29 Correct 6 ms 504 KB Output is correct
30 Correct 5 ms 504 KB Output is correct
31 Correct 5 ms 504 KB Output is correct
32 Correct 5 ms 504 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 931 ms 239896 KB Output is correct
3 Correct 925 ms 239668 KB Output is correct
4 Correct 893 ms 230604 KB Output is correct
5 Correct 911 ms 235452 KB Output is correct
6 Correct 941 ms 242284 KB Output is correct
7 Correct 951 ms 255696 KB Output is correct
8 Correct 920 ms 240412 KB Output is correct
9 Correct 922 ms 249248 KB Output is correct
10 Correct 876 ms 233296 KB Output is correct
11 Correct 926 ms 238720 KB Output is correct
12 Correct 938 ms 243176 KB Output is correct
13 Correct 949 ms 242820 KB Output is correct
14 Execution timed out 1008 ms 257480 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Execution timed out 1114 ms 262124 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 302 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 5 ms 504 KB Output is correct
12 Correct 5 ms 504 KB Output is correct
13 Correct 5 ms 504 KB Output is correct
14 Correct 5 ms 500 KB Output is correct
15 Correct 5 ms 504 KB Output is correct
16 Correct 5 ms 504 KB Output is correct
17 Correct 5 ms 504 KB Output is correct
18 Correct 5 ms 504 KB Output is correct
19 Correct 5 ms 504 KB Output is correct
20 Correct 5 ms 504 KB Output is correct
21 Correct 5 ms 504 KB Output is correct
22 Correct 5 ms 504 KB Output is correct
23 Correct 5 ms 504 KB Output is correct
24 Correct 5 ms 504 KB Output is correct
25 Correct 5 ms 504 KB Output is correct
26 Correct 6 ms 504 KB Output is correct
27 Correct 6 ms 504 KB Output is correct
28 Correct 5 ms 504 KB Output is correct
29 Correct 6 ms 504 KB Output is correct
30 Correct 5 ms 504 KB Output is correct
31 Correct 5 ms 504 KB Output is correct
32 Correct 5 ms 504 KB Output is correct
33 Execution timed out 1063 ms 237756 KB Time limit exceeded
34 Halted 0 ms 0 KB -