oj.uz

Submission #828005

# Submission time Handle Problem Language Result Execution time Memory
828005 2023-08-17T01:14:22 Z physics07 Radio Towers (IOI22_towers) C++17
31 / 100
 973 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;
    if(tree.query(l, r)-mtree.query(l, r)<d) return 1;
    int cnt=0;
    if(rt[l]==n || tree.query(l, rt[l]-1)>=d+a[l]) cnt++;
    if(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 429 ms 28684 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 1 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 1 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 638 ms 31080 KB Output is correct
2 Correct 848 ms 31128 KB Output is correct
3 Correct 886 ms 31048 KB Output is correct
4 Correct 897 ms 31048 KB Output is correct
5 Correct 942 ms 31052 KB Output is correct
6 Correct 936 ms 31104 KB Output is correct
7 Correct 907 ms 31020 KB Output is correct
8 Correct 856 ms 31272 KB Output is correct
9 Correct 826 ms 31528 KB Output is correct
10 Correct 909 ms 31248 KB Output is correct
11 Correct 775 ms 31268 KB Output is correct
12 Correct 973 ms 31272 KB Output is correct
13 Correct 935 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 31020 KB Output is correct
18 Correct 66 ms 31124 KB Output is correct
19 Correct 62 ms 31116 KB Output is correct
20 Correct 46 ms 31548 KB Output is correct
21 Correct 52 ms 31276 KB Output is correct
22 Correct 61 ms 31080 KB Output is correct
23 Correct 60 ms 31020 KB Output is correct
24 Correct 60 ms 31020 KB Output is correct
25 Correct 47 ms 31548 KB Output is correct
26 Correct 58 ms 31124 KB Output is correct
27 Correct 2 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 251 ms 7948 KB Output is correct
2 Correct 807 ms 31080 KB Output is correct
3 Correct 687 ms 31136 KB Output is correct
4 Correct 906 ms 31140 KB Output is correct
5 Correct 710 ms 31020 KB Output is correct
6 Correct 825 ms 31148 KB Output is correct
7 Correct 890 ms 31088 KB Output is correct
8 Correct 735 ms 31200 KB Output is correct
9 Correct 676 ms 31508 KB Output is correct
10 Correct 770 ms 31232 KB Output is correct
11 Correct 831 ms 31240 KB Output is correct
12 Correct 58 ms 31124 KB Output is correct
13 Correct 58 ms 31100 KB Output is correct
14 Correct 58 ms 31120 KB Output is correct
15 Correct 46 ms 31448 KB Output is correct
16 Correct 53 ms 31152 KB Output is correct
17 Correct 69 ms 30932 KB Output is correct
18 Correct 74 ms 31136 KB Output is correct
19 Correct 58 ms 31084 KB Output is correct
20 Correct 59 ms 31148 KB Output is correct
21 Correct 60 ms 31024 KB Output is correct
22 Correct 64 ms 31148 KB Output is correct
23 Correct 59 ms 31140 KB Output is correct
24 Correct 48 ms 31312 KB Output is correct
25 Correct 47 ms 31460 KB Output is correct
26 Correct 56 ms 31168 KB Output is correct
27 Correct 53 ms 31516 KB Output is correct
28 Correct 1 ms 904 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 656 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 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 1 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 1 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 429 ms 28684 KB 11th lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -