oj.uz

Submission #1119836

# Submission time Handle Problem Language Result Execution time Memory
1119836 2024-11-27T13:44:47 Z Aviansh Lasers (NOI19_lasers) C++17
10 / 100
 825 ms 262144 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;
        node *laz;
        node def;
        int no;
    public:
        lazySparseSegTree(int siz, int nodes){
            st = new node[nodes];
            laz = new node[nodes];
            def.val=0;
            def.left=-1;
            def.right=-1;
            fill(st,st+nodes,def);
            fill(laz,laz+nodes,def);
            n=siz-1;
            no=nodes;
        }

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

        void pushdown(int ind, int l, int r){
            if(laz[ind].val==0){
                return;
            }
            if(l==r){
                st[ind].val=laz[ind].val*(r-l+1);
                return;
            }
            makeKids(ind);
            int mid = (l+r)/2;
            laz[laz[ind].left].val=laz[ind].val;
            laz[laz[ind].right].val=laz[ind].val;
            st[st[ind].left].val=laz[ind].val*(mid-l+1);
            st[st[ind].right].val=laz[ind].val*(r-mid);
            laz[ind].val=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=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,5e6);
    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 29 ms 117840 KB Output is correct
2 Correct 34 ms 117852 KB Output is correct
3 Correct 24 ms 117840 KB Output is correct
4 Correct 33 ms 117840 KB Output is correct
5 Correct 23 ms 117840 KB Output is correct
6 Correct 33 ms 117840 KB Output is correct
7 Correct 26 ms 117840 KB Output is correct
8 Correct 24 ms 117888 KB Output is correct
9 Correct 30 ms 117840 KB Output is correct
10 Correct 25 ms 117840 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 117840 KB Output is correct
2 Correct 34 ms 117852 KB Output is correct
3 Correct 24 ms 117840 KB Output is correct
4 Correct 33 ms 117840 KB Output is correct
5 Correct 23 ms 117840 KB Output is correct
6 Correct 33 ms 117840 KB Output is correct
7 Correct 26 ms 117840 KB Output is correct
8 Correct 24 ms 117888 KB Output is correct
9 Correct 30 ms 117840 KB Output is correct
10 Correct 25 ms 117840 KB Output is correct
11 Correct 25 ms 117924 KB Output is correct
12 Correct 141 ms 146416 KB Output is correct
13 Correct 24 ms 117840 KB Output is correct
14 Correct 24 ms 117792 KB Output is correct
15 Correct 28 ms 117812 KB Output is correct
16 Correct 29 ms 117840 KB Output is correct
17 Runtime error 825 ms 262144 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 117840 KB Output is correct
2 Correct 32 ms 117840 KB Output is correct
3 Incorrect 24 ms 117840 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

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

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 117840 KB Output is correct
2 Correct 34 ms 117852 KB Output is correct
3 Correct 24 ms 117840 KB Output is correct
4 Correct 33 ms 117840 KB Output is correct
5 Correct 23 ms 117840 KB Output is correct
6 Correct 33 ms 117840 KB Output is correct
7 Correct 26 ms 117840 KB Output is correct
8 Correct 24 ms 117888 KB Output is correct
9 Correct 30 ms 117840 KB Output is correct
10 Correct 25 ms 117840 KB Output is correct
11 Correct 25 ms 117924 KB Output is correct
12 Correct 141 ms 146416 KB Output is correct
13 Correct 24 ms 117840 KB Output is correct
14 Correct 24 ms 117792 KB Output is correct
15 Correct 28 ms 117812 KB Output is correct
16 Correct 29 ms 117840 KB Output is correct
17 Runtime error 825 ms 262144 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -