oj.uz

Submission #828004

# Submission time Handle Problem Language Result Execution time Memory
828004 2023-08-17T01:11:20 Z physics07 Radio Towers (IOI22_towers) C++17
31 / 100
 933 ms 31548 KB 
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int inf=1e9+7;
int n, lt[100001], rt[100001], cut[100001], root[100001];
stack<int> stk;
vector<pair<int, int>> v;
vector<int> del, a;
struct maxseg {
    int tree[100001*2], sz;
    void init(int n) {sz=n;}
    void update(int idx, int v) {
        for(tree[idx+=sz]+=v; idx>1; idx>>=1) tree[idx>>1]=max(tree[idx], tree[idx^1]);
    }
    int query(int l, int r) {
        int res=0;
        for(l+=sz, r+=sz; l<=r; l>>=1, r>>=1) {
            if(l&1) res=max(res, tree[l++]);
            if(~r&1) res=max(res, tree[r--]);
        }
        return res;
    }
} tree;
struct minseg {
    int tree[100001*2], sz;
    void init(int n) {sz=n;}
    void update(int idx, int v) {
        for(tree[idx+=sz]+=v; idx>1; idx>>=1) tree[idx>>1]=min(tree[idx], tree[idx^1]);
    }
    int query(int l, int r) {
        int res=0;
        for(l+=sz, r+=sz; l<=r; l>>=1, r>>=1) {
            if(l&1) res=min(res, tree[l++]);
            if(~r&1) res=min(res, tree[r--]);
        }
        return res;
    }
} mtree;
struct PST {
    struct Node {
        int v, l, r;
    };
    vector<Node> tree;
    void mak() {tree.push_back({0, -1, -1});}
    void init(int node, int s, int e) {
        if(s==e) return;
        tree[node].l=(int)tree.size();
        mak();
        tree[node].r=(int)tree.size();
        mak();
        int m=s+e>>1;
        init(tree[node].l, s, m);
        init(tree[node].r, m+1, e);
    }
    void update(int node, int s, int e, int idx, int v, int prv) {
        if(s>idx || e<idx) return;
        tree[node]=tree[prv];
        tree[node].v+=v;
        if(s==e) return;
        int m=s+e>>1;
        if(idx<=m) {
            tree[node].l=(int)tree.size();
            mak();
            update(tree[node].l, s, m, idx, v, tree[prv].l);
        }
        else {
            tree[node].r=(int)tree.size();
            mak();
            update(tree[node].r, m+1, e, idx, v, tree[prv].r);
        }
    }
    int query(int node, int s, int e, int l, int r) {
        if(s>r || e<l) return 0;
        if(s>=l && e<=r) return tree[node].v;
        int m=s+e>>1;
        return query(tree[node].l, s, m, l, r)+query(tree[node].r, m+1, e, l, r);
    }
} pst;
void init(int N, vector<int> A) {
    n=N;
    for(auto i: A) a.push_back(i);
    tree.init(n);
    mtree.init(n);
    for(int i=0; i<n; i++) tree.update(i, a[i]);
    for(int i=0; i<n; i++) mtree.update(i, a[i]);
    for(int i=0; i<n; i++) {
        while(!stk.empty() && a[stk.top()]>a[i]) stk.pop();
        lt[i]=(stk.empty() ? -1 : stk.top());
        stk.push(i);
    }
    while(!stk.empty()) stk.pop();
    for(int i=n-1; i>=0; i--) {
        while(!stk.empty() && a[stk.top()]>a[i]) stk.pop();
        rt[i]=(stk.empty() ? n : stk.top());
        stk.push(i);
    }
    for(int i=0; i<n; i++) {
        int curr=inf;
        if(lt[i]>=0) curr=min(curr, tree.query(lt[i]+1, i));
        if(rt[i]<n) curr=min(curr, tree.query(i, rt[i]-1));
        if(curr==inf) cut[i]=inf;
        else if(curr>a[i]) cut[i]=curr-a[i];
        else cut[i]=0;
        v.push_back({cut[i], i});
        del.push_back(cut[i]);
    }
    del.push_back(inf);
    sort(del.begin(), del.end());
    sort(v.begin(), v.end());
    root[n]=0;
    pst.mak();
    pst.init(0, 0, n-1);
    for(int i=n-1; i>=0; i--) {
        root[i]=(int)pst.tree.size();
        pst.mak();
        pst.update(root[i], 0, n-1, v[i].second, 1, root[i+1]);
    }
}

int max_towers(int l, int r, int d) {
    if(l==r || r==l+1) return 1;
    int cnt=0;
    if(a[l]==mtree.query(l, r) || rt[l]==n || tree.query(l, rt[l]-1)>=d+a[l]) cnt++;
    if(a[r]==mtree.query(l, r) || lt[r]==-1 || tree.query(lt[r]+1, r)>=d+a[r]) cnt++;
    int idx=lower_bound(del.begin(), del.end(), d)-del.begin();
    return cnt+pst.query(root[idx], 0, n-1, l+1, r-1);
}

Compilation message

towers.cpp: In member function 'void PST::init(int, int, int)':
towers.cpp:52:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         int m=s+e>>1;
      |               ~^~
towers.cpp: In member function 'void PST::update(int, int, int, int, int, int)':
towers.cpp:61:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |         int m=s+e>>1;
      |               ~^~
towers.cpp: In member function 'int PST::query(int, int, int, int, int)':
towers.cpp:76:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |         int m=s+e>>1;
      |               ~^~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 359 ms 28716 KB 11th lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 916 KB Output is correct
3 Correct 1 ms 916 KB Output is correct
4 Correct 1 ms 916 KB Output is correct
5 Correct 2 ms 916 KB Output is correct
6 Correct 1 ms 916 KB Output is correct
7 Incorrect 1 ms 916 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 916 KB Output is correct
3 Correct 1 ms 916 KB Output is correct
4 Correct 1 ms 916 KB Output is correct
5 Correct 2 ms 916 KB Output is correct
6 Correct 1 ms 916 KB Output is correct
7 Incorrect 1 ms 916 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 667 ms 31040 KB Output is correct
2 Correct 857 ms 31140 KB Output is correct
3 Correct 902 ms 31012 KB Output is correct
4 Correct 878 ms 31148 KB Output is correct
5 Correct 793 ms 31116 KB Output is correct
6 Correct 636 ms 31020 KB Output is correct
7 Correct 870 ms 31032 KB Output is correct
8 Correct 933 ms 31268 KB Output is correct
9 Correct 914 ms 31532 KB Output is correct
10 Correct 793 ms 31220 KB Output is correct
11 Correct 856 ms 31276 KB Output is correct
12 Correct 714 ms 31272 KB Output is correct
13 Correct 738 ms 31532 KB Output is correct
14 Correct 0 ms 208 KB Output is correct
15 Correct 1 ms 920 KB Output is correct
16 Correct 1 ms 916 KB Output is correct
17 Correct 59 ms 31064 KB Output is correct
18 Correct 60 ms 31124 KB Output is correct
19 Correct 65 ms 31116 KB Output is correct
20 Correct 46 ms 31532 KB Output is correct
21 Correct 51 ms 31272 KB Output is correct
22 Correct 60 ms 31096 KB Output is correct
23 Correct 60 ms 31040 KB Output is correct
24 Correct 67 ms 31120 KB Output is correct
25 Correct 58 ms 31532 KB Output is correct
26 Correct 55 ms 31160 KB Output is correct
27 Correct 1 ms 916 KB Output is correct
28 Correct 1 ms 916 KB Output is correct
29 Correct 1 ms 916 KB Output is correct
30 Correct 1 ms 916 KB Output is correct
31 Correct 1 ms 916 KB Output is correct
32 Correct 1 ms 916 KB Output is correct
33 Correct 1 ms 916 KB Output is correct
34 Correct 1 ms 916 KB Output is correct
35 Correct 1 ms 916 KB Output is correct
36 Correct 1 ms 920 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 7920 KB Output is correct
2 Correct 840 ms 31036 KB Output is correct
3 Correct 759 ms 31020 KB Output is correct
4 Correct 731 ms 31140 KB Output is correct
5 Correct 838 ms 31144 KB Output is correct
6 Correct 730 ms 31040 KB Output is correct
7 Correct 803 ms 31056 KB Output is correct
8 Correct 718 ms 31268 KB Output is correct
9 Correct 686 ms 31528 KB Output is correct
10 Correct 753 ms 31144 KB Output is correct
11 Correct 699 ms 31148 KB Output is correct
12 Correct 59 ms 31020 KB Output is correct
13 Correct 60 ms 31012 KB Output is correct
14 Correct 60 ms 31132 KB Output is correct
15 Correct 47 ms 31548 KB Output is correct
16 Correct 65 ms 31092 KB Output is correct
17 Correct 60 ms 31000 KB Output is correct
18 Correct 59 ms 31148 KB Output is correct
19 Correct 67 ms 31016 KB Output is correct
20 Correct 69 ms 31020 KB Output is correct
21 Correct 62 ms 31116 KB Output is correct
22 Correct 59 ms 31020 KB Output is correct
23 Correct 63 ms 31156 KB Output is correct
24 Correct 45 ms 31188 KB Output is correct
25 Correct 47 ms 31460 KB Output is correct
26 Correct 54 ms 31176 KB Output is correct
27 Correct 54 ms 31444 KB Output is correct
28 Correct 1 ms 916 KB Output is correct
29 Correct 1 ms 916 KB Output is correct
30 Correct 2 ms 916 KB Output is correct
31 Correct 1 ms 916 KB Output is correct
32 Correct 1 ms 920 KB Output is correct
33 Correct 1 ms 592 KB Output is correct
34 Correct 2 ms 916 KB Output is correct
35 Correct 1 ms 916 KB Output is correct
36 Correct 2 ms 916 KB Output is correct
37 Correct 1 ms 916 KB Output is correct
38 Correct 1 ms 916 KB Output is correct
39 Correct 1 ms 916 KB Output is correct
40 Correct 1 ms 920 KB Output is correct
41 Correct 2 ms 916 KB Output is correct
42 Correct 1 ms 920 KB Output is correct
43 Correct 1 ms 916 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 916 KB Output is correct
3 Correct 1 ms 916 KB Output is correct
4 Correct 1 ms 916 KB Output is correct
5 Correct 2 ms 916 KB Output is correct
6 Correct 1 ms 916 KB Output is correct
7 Incorrect 1 ms 916 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 359 ms 28716 KB 11th lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -