oj.uz

Submission #206546

# Submission time Handle Problem Language Result Execution time Memory
206546 2020-03-03T22:04:10 Z osaaateiasavtnl Fire (JOI20_ho_t5) C++14
100 / 100
 394 ms 90568 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
 
const int N = 2e5 + 7;
int n, q, a[N], l[N], r[N];
vector <int> d[N];
vector <ii> mem[N], meml[N];
 
void add(int l, int r, int i, int x) {
    mem[l].app(mp(i, x));
    mem[r + 1].app(mp(i, -x));    
}   
void addl(int l, int r, int i, int x) {
    meml[l].app(mp(i, x));
    meml[r + 1].app(mp(i, -x));
}   
 
int link_l[N], link_r[N];
int ans[N];
 
struct Fen {
int f[N];
void clear() {
    for (int i = 0; i < N; ++i) f[i] = 0;
}   
void add(int i, int x) {
    for (; i < N; i |= i + 1) 
        f[i] += x;
}   
int get(int i) {
    int ans = 0;
    for (; i >= 0; i &= i + 1, --i) ans += f[i];
    return ans;
}   
int get(int l, int r) {
    return get(r) - get(l - 1);
}   
} f, fl;
 
int pref_mx[N], pref_sum[N];
//bigger left, not less right
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        pref_mx[i + 1] = max(pref_mx[i], a[i]);
        pref_sum[i + 1] = pref_sum[i] + pref_mx[i + 1];
    }
    for (int i = 0; i < q; ++i) {
        int t;
        cin >> t >> l[i] >> r[i];
        --l[i]; --r[i];
        d[t + 1].app(i);
    }   
    vector <int> s;
    for (int i = 0; i < n; ++i) {
        while (s.size() && a[s.back()] <= a[i]) {
            link_r[s.back()] = i;
            s.pop_back();
        }   
        s.app(i);                    
    }   
    for (int e : s)
        link_r[e] = n;
    s.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (s.size() && a[s.back()] < a[i]) {
            link_l[s.back()] = i;
            s.pop_back();
        }   
        s.app(i);
    }   
    for (int e : s)
        link_l[e] = -1;
    s.clear();
    for (int i = 0; i < n; ++i) {
        if (link_r[i] - i < i - link_l[i]) {
            for (int j = i; j < link_r[i]; ++j) {
                int len1 = j - i + 1;
                int len2 = j - link_l[i];
                add(len1, len2, j, a[i]);
            }   
        }
        else {
            for (int j = link_l[i] + 1; j <= i; ++j) {
                int len1 = i - j + 1;
                int len2 = link_r[i] - j;
                if (link_r[i] == n)
                    len2 = N - 2;
                addl(len1, len2, j, a[i]);
            }            
        }   
    }   
 
    f.clear();
    fl.clear();
    for (int len = 1; len < N; ++len) {
        for (auto e : mem[len]) 
            f.add(e.f, e.s);
        for (auto e : meml[len]) {
            fl.add(e.f, e.s);
        }
        for (auto e : d[len]) {
            ans[e] += f.get(l[e], r[e]);
            if (l[e] + 1 < len) {
                int t = min(len - 1, r[e] + 1);
                ans[e] += pref_sum[t] - pref_sum[l[e]];   
                l[e] = t;
            }   
            if (l[e] <= r[e])
                ans[e] += fl.get(l[e] - len + 1, r[e] - len + 1);
        }
    }   
    for (int i = 0; i < q; ++i)
        cout << ans[i] << '\n';
}

Subtask #1
1.0 / 1.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 17656 KB Output is correct
2 Correct 316 ms 85512 KB Output is correct
3 Correct 298 ms 84836 KB Output is correct
4 Correct 315 ms 86116 KB Output is correct
5 Correct 302 ms 84836 KB Output is correct
6 Correct 299 ms 85092 KB Output is correct
7 Correct 304 ms 85732 KB Output is correct
8 Correct 309 ms 89780 KB Output is correct
9 Correct 297 ms 84068 KB Output is correct
10 Correct 302 ms 82532 KB Output is correct
11 Correct 306 ms 85980 KB Output is correct
12 Correct 293 ms 82744 KB Output is correct
13 Correct 299 ms 86372 KB Output is correct
14 Correct 301 ms 84452 KB Output is correct
15 Correct 298 ms 83684 KB Output is correct
16 Correct 299 ms 85604 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 17656 KB Output is correct
2 Correct 380 ms 84556 KB Output is correct
3 Correct 364 ms 82760 KB Output is correct
4 Correct 394 ms 87632 KB Output is correct
5 Correct 360 ms 84040 KB Output is correct
6 Correct 383 ms 88656 KB Output is correct
7 Correct 377 ms 89156 KB Output is correct
8 Correct 377 ms 86092 KB Output is correct
9 Correct 374 ms 85196 KB Output is correct
10 Correct 374 ms 90192 KB Output is correct
11 Correct 388 ms 87248 KB Output is correct
12 Correct 364 ms 85836 KB Output is correct
13 Correct 382 ms 86864 KB Output is correct
14 Correct 361 ms 85188 KB Output is correct
15 Correct 388 ms 88396 KB Output is correct
16 Correct 378 ms 86220 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 48352 KB Output is correct
2 Correct 246 ms 48228 KB Output is correct
3 Correct 254 ms 49124 KB Output is correct
4 Correct 250 ms 48220 KB Output is correct
5 Correct 244 ms 48412 KB Output is correct
6 Correct 242 ms 48476 KB Output is correct
7 Correct 238 ms 48864 KB Output is correct
8 Correct 247 ms 48732 KB Output is correct
9 Correct 244 ms 48360 KB Output is correct
10 Correct 264 ms 48816 KB Output is correct
11 Correct 249 ms 48612 KB Output is correct
12 Correct 255 ms 48476 KB Output is correct
13 Correct 247 ms 48356 KB Output is correct
14 Correct 239 ms 48484 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 17656 KB Output is correct
2 Correct 16 ms 17656 KB Output is correct
3 Correct 16 ms 17656 KB Output is correct
4 Correct 16 ms 17656 KB Output is correct
5 Correct 16 ms 17660 KB Output is correct
6 Correct 16 ms 17656 KB Output is correct
7 Correct 16 ms 17656 KB Output is correct
8 Correct 17 ms 17656 KB Output is correct
9 Correct 16 ms 17784 KB Output is correct
10 Correct 16 ms 17656 KB Output is correct
11 Correct 16 ms 17656 KB Output is correct
12 Correct 16 ms 17656 KB Output is correct
13 Correct 16 ms 17656 KB Output is correct
14 Correct 16 ms 17656 KB Output is correct
15 Correct 16 ms 17656 KB Output is correct
16 Correct 16 ms 17632 KB Output is correct
17 Correct 16 ms 17656 KB Output is correct
18 Correct 16 ms 17656 KB Output is correct
19 Correct 17 ms 17656 KB Output is correct
20 Correct 16 ms 17660 KB Output is correct
21 Correct 16 ms 17656 KB Output is correct
22 Correct 16 ms 17656 KB Output is correct
23 Correct 16 ms 17656 KB Output is correct
24 Correct 16 ms 17656 KB Output is correct
25 Correct 17 ms 17652 KB Output is correct
26 Correct 17 ms 17784 KB Output is correct
27 Correct 16 ms 17656 KB Output is correct
28 Correct 16 ms 17656 KB Output is correct
29 Correct 16 ms 17656 KB Output is correct
30 Correct 16 ms 17660 KB Output is correct
31 Correct 16 ms 17656 KB Output is correct
32 Correct 16 ms 17656 KB Output is correct
33 Correct 394 ms 88516 KB Output is correct
34 Correct 394 ms 88372 KB Output is correct
35 Correct 388 ms 90568 KB Output is correct
36 Correct 388 ms 87220 KB Output is correct
37 Correct 375 ms 87116 KB Output is correct
38 Correct 382 ms 85840 KB Output is correct
39 Correct 389 ms 86464 KB Output is correct
40 Correct 384 ms 86480 KB Output is correct
41 Correct 392 ms 86736 KB Output is correct
42 Correct 379 ms 85308 KB Output is correct
43 Correct 347 ms 87756 KB Output is correct
44 Correct 331 ms 85452 KB Output is correct
45 Correct 327 ms 84304 KB Output is correct
46 Correct 379 ms 87092 KB Output is correct
47 Correct 335 ms 83656 KB Output is correct
48 Correct 329 ms 82620 KB Output is correct
49 Correct 330 ms 85832 KB Output is correct
50 Correct 348 ms 89292 KB Output is correct
51 Correct 335 ms 86476 KB Output is correct
52 Correct 340 ms 84424 KB Output is correct
53 Correct 343 ms 84176 KB Output is correct
54 Correct 342 ms 84300 KB Output is correct
55 Correct 346 ms 84676 KB Output is correct
56 Correct 343 ms 85832 KB Output is correct
57 Correct 352 ms 85372 KB Output is correct
58 Correct 344 ms 87884 KB Output is correct
59 Correct 316 ms 85512 KB Output is correct
60 Correct 298 ms 84836 KB Output is correct
61 Correct 315 ms 86116 KB Output is correct
62 Correct 302 ms 84836 KB Output is correct
63 Correct 299 ms 85092 KB Output is correct
64 Correct 304 ms 85732 KB Output is correct
65 Correct 309 ms 89780 KB Output is correct
66 Correct 297 ms 84068 KB Output is correct
67 Correct 302 ms 82532 KB Output is correct
68 Correct 306 ms 85980 KB Output is correct
69 Correct 293 ms 82744 KB Output is correct
70 Correct 299 ms 86372 KB Output is correct
71 Correct 301 ms 84452 KB Output is correct
72 Correct 298 ms 83684 KB Output is correct
73 Correct 299 ms 85604 KB Output is correct
74 Correct 380 ms 84556 KB Output is correct
75 Correct 364 ms 82760 KB Output is correct
76 Correct 394 ms 87632 KB Output is correct
77 Correct 360 ms 84040 KB Output is correct
78 Correct 383 ms 88656 KB Output is correct
79 Correct 377 ms 89156 KB Output is correct
80 Correct 377 ms 86092 KB Output is correct
81 Correct 374 ms 85196 KB Output is correct
82 Correct 374 ms 90192 KB Output is correct
83 Correct 388 ms 87248 KB Output is correct
84 Correct 364 ms 85836 KB Output is correct
85 Correct 382 ms 86864 KB Output is correct
86 Correct 361 ms 85188 KB Output is correct
87 Correct 388 ms 88396 KB Output is correct
88 Correct 378 ms 86220 KB Output is correct
89 Correct 246 ms 48352 KB Output is correct
90 Correct 246 ms 48228 KB Output is correct
91 Correct 254 ms 49124 KB Output is correct
92 Correct 250 ms 48220 KB Output is correct
93 Correct 244 ms 48412 KB Output is correct
94 Correct 242 ms 48476 KB Output is correct
95 Correct 238 ms 48864 KB Output is correct
96 Correct 247 ms 48732 KB Output is correct
97 Correct 244 ms 48360 KB Output is correct
98 Correct 264 ms 48816 KB Output is correct
99 Correct 249 ms 48612 KB Output is correct
100 Correct 255 ms 48476 KB Output is correct
101 Correct 247 ms 48356 KB Output is correct
102 Correct 239 ms 48484 KB Output is correct