oj.uz

Submission #206544

# Submission time Handle Problem Language Result Execution time Memory
206544 2020-03-03T21:55:01 Z osaaateiasavtnl Fire (JOI20_ho_t5) C++14
0 / 100
 1000 ms 90192 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) {
    if (l <= r) {
        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]);
                //cout << "addl " << len1 << ' ' << len2 << ' ' << j << ' ' << a[i] << endl;
            }            
        }   
    }   
 
    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);
            //cout << "addf " << len << ' ' << e.f << ' ' << e.s << endl;
        }
        for (auto e : d[len]) {
            ans[e] += f.get(l[e], r[e]);
            for (int i = l[e]; i <= r[e]; ++i)
                if (i < len)
                    ans[e] += pref_mx[i + 1];
                else
                    ans[e] += fl.get(i - len + 1, i - len + 1);
            /*
            if (l[e] + 1 < len) {
                int t = min(len, 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';
 
    #ifdef HOME
    cout << Time << endl;
    #endif
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 17656 KB Output is correct
2 Correct 15 ms 17656 KB Output is correct
3 Incorrect 15 ms 17656 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 17656 KB Output is correct
2 Execution timed out 1096 ms 81104 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 17656 KB Output is correct
2 Correct 365 ms 84552 KB Output is correct
3 Correct 364 ms 82760 KB Output is correct
4 Correct 415 ms 87732 KB Output is correct
5 Correct 355 ms 84036 KB Output is correct
6 Correct 389 ms 88608 KB Output is correct
7 Correct 365 ms 89112 KB Output is correct
8 Correct 369 ms 86088 KB Output is correct
9 Correct 376 ms 85204 KB Output is correct
10 Incorrect 375 ms 90192 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1099 ms 47068 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 17656 KB Output is correct
2 Correct 15 ms 17656 KB Output is correct
3 Incorrect 15 ms 17656 KB Output isn't correct
4 Halted 0 ms 0 KB -