oj.uz

Submission #1119839

# Submission time Handle Problem Language Result Execution time Memory
1119839 2024-11-27T13:48:13 Z Aviansh Lasers (NOI19_lasers) C++17
24 / 100
 391 ms 186212 KB 
#include <bits/stdc++.h>

using namespace std;

struct node{
    int val;
    int left=-1;
    int right=-1;
};

class lazySparseSegTree{
    private:
        int cr = 1;
        int n;
        node *st;
        int *laz;
        node def;
        int no;
    public:
        lazySparseSegTree(int siz, int nodes){
            st = new node[nodes];
            laz = new int[nodes];
            def.val=0;
            def.left=-1;
            def.right=-1;
            fill(st,st+nodes,def);
            fill(laz,laz+nodes,0);
            n=siz-1;
            no=nodes;
        }

        void makeKids(int ind){
            if(st[ind].left==-1){
                st[ind].left=cr++;
            }
            if(st[ind].right==-1){
                st[ind].right=cr++;
            }
            assert(cr<no);
        }

        void pushdown(int ind, int l, int r){
            if(laz[ind]==0){
                return;
            }
            if(l==r){
                st[ind].val=laz[ind]*(r-l+1);
                return;
            }
            makeKids(ind);
            int mid = (l+r)/2;
            laz[st[ind].left]=laz[ind];
            laz[st[ind].right]=laz[ind];
            st[st[ind].left].val=laz[ind]*(mid-l+1);
            st[st[ind].right].val=laz[ind]*(r-mid);
            laz[ind]=0;
        }

        void realUpdate(int l, int r, int s, int e, int val, int ind){
            if(r<s||l>e){
                return;
            }
            if(s<=l&&r<=e){
                laz[ind]=val;
                st[ind].val=(r-l+1)*val;
                return;
            }
            int mid = (l+r)/2;
            pushdown(ind,l,r);
            makeKids(ind);
            realUpdate(l,mid,s,e,val,st[ind].left);
            realUpdate(mid+1,r,s,e,val,st[ind].right);
            st[ind].val=st[st[ind].left].val+st[st[ind].right].val;
        }
        void update(int l, int r, int val){
            realUpdate(0,n,l,r,val,0);
        }
        int realQuery(int l, int r, int s, int e, int ind){
            if(r<s||l>e){
                return 0;
            }
            pushdown(ind,l,r);
            if(s<=l&&r<=e){
                return st[ind].val;
            }
            int mid = (l+r)/2;
            makeKids(ind);
            return realQuery(l,mid,s,e,st[ind].left)+realQuery(mid+1,r,s,e,st[ind].right);
        }
        int query(int l, int r){
            return realQuery(0,n,l,r,0);
        }
};

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int l,r;
    cin >> l >> r;
    vector<int>walls[r];
    lazySparseSegTree lsst(l,1e7);
    int sums[r];
    for(int i = 0;i<r;i++){
        int x;
        cin >> x;
        sums[i]=0;
        for(int j = 0;j<x;j++){
            int c;
            cin >> c;
            sums[i]+=c;
            walls[i].push_back(c);
        }
    }
    for(int i = 0;i<r;i++){
        int curl=0;
        for(int w : walls[i]){
            int lef = sums[i]-curl;
            lef=l-lef;
            int right = curl+w-1;
            if(right<lef){
                continue;
            }
            lsst.update(lef,right,1);
            curl+=w;
        }
    }
    cout << lsst.query(0,l-1);
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 157008 KB Output is correct
2 Correct 29 ms 157008 KB Output is correct
3 Correct 26 ms 156792 KB Output is correct
4 Correct 34 ms 156784 KB Output is correct
5 Correct 32 ms 156788 KB Output is correct
6 Correct 27 ms 157008 KB Output is correct
7 Correct 34 ms 157008 KB Output is correct
8 Correct 35 ms 156820 KB Output is correct
9 Correct 28 ms 157008 KB Output is correct
10 Correct 27 ms 157000 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 157008 KB Output is correct
2 Correct 29 ms 157008 KB Output is correct
3 Correct 26 ms 156792 KB Output is correct
4 Correct 34 ms 156784 KB Output is correct
5 Correct 32 ms 156788 KB Output is correct
6 Correct 27 ms 157008 KB Output is correct
7 Correct 34 ms 157008 KB Output is correct
8 Correct 35 ms 156820 KB Output is correct
9 Correct 28 ms 157008 KB Output is correct
10 Correct 27 ms 157000 KB Output is correct
11 Correct 37 ms 157008 KB Output is correct
12 Correct 126 ms 185672 KB Output is correct
13 Correct 31 ms 157000 KB Output is correct
14 Correct 27 ms 156856 KB Output is correct
15 Correct 30 ms 157072 KB Output is correct
16 Correct 27 ms 157008 KB Output is correct
17 Correct 391 ms 186212 KB Output is correct
18 Correct 27 ms 157012 KB Output is correct
19 Correct 36 ms 157012 KB Output is correct
20 Correct 30 ms 156984 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 158952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 156852 KB Output is correct
2 Correct 29 ms 156884 KB Output is correct
3 Incorrect 29 ms 157000 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 158952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 157008 KB Output is correct
2 Correct 29 ms 157008 KB Output is correct
3 Correct 26 ms 156792 KB Output is correct
4 Correct 34 ms 156784 KB Output is correct
5 Correct 32 ms 156788 KB Output is correct
6 Correct 27 ms 157008 KB Output is correct
7 Correct 34 ms 157008 KB Output is correct
8 Correct 35 ms 156820 KB Output is correct
9 Correct 28 ms 157008 KB Output is correct
10 Correct 27 ms 157000 KB Output is correct
11 Correct 37 ms 157008 KB Output is correct
12 Correct 126 ms 185672 KB Output is correct
13 Correct 31 ms 157000 KB Output is correct
14 Correct 27 ms 156856 KB Output is correct
15 Correct 30 ms 157072 KB Output is correct
16 Correct 27 ms 157008 KB Output is correct
17 Correct 391 ms 186212 KB Output is correct
18 Correct 27 ms 157012 KB Output is correct
19 Correct 36 ms 157012 KB Output is correct
20 Correct 30 ms 156984 KB Output is correct
21 Incorrect 87 ms 158952 KB Output isn't correct
22 Halted 0 ms 0 KB -