oj.uz

Submission #1119838

# Submission time Handle Problem Language Result Execution time Memory
1119838 2024-11-27T13:47:46 Z Aviansh Lasers (NOI19_lasers) C++17
10 / 100
 407 ms 218496 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,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 16 ms 78632 KB Output is correct
2 Correct 17 ms 78684 KB Output is correct
3 Correct 16 ms 78672 KB Output is correct
4 Correct 16 ms 78672 KB Output is correct
5 Correct 17 ms 78672 KB Output is correct
6 Correct 16 ms 78672 KB Output is correct
7 Correct 21 ms 78672 KB Output is correct
8 Correct 15 ms 78644 KB Output is correct
9 Correct 15 ms 78692 KB Output is correct
10 Correct 17 ms 78648 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 78632 KB Output is correct
2 Correct 17 ms 78684 KB Output is correct
3 Correct 16 ms 78672 KB Output is correct
4 Correct 16 ms 78672 KB Output is correct
5 Correct 17 ms 78672 KB Output is correct
6 Correct 16 ms 78672 KB Output is correct
7 Correct 21 ms 78672 KB Output is correct
8 Correct 15 ms 78644 KB Output is correct
9 Correct 15 ms 78692 KB Output is correct
10 Correct 17 ms 78648 KB Output is correct
11 Correct 16 ms 78652 KB Output is correct
12 Correct 104 ms 107280 KB Output is correct
13 Correct 16 ms 78672 KB Output is correct
14 Correct 17 ms 78672 KB Output is correct
15 Correct 17 ms 78672 KB Output is correct
16 Correct 17 ms 78648 KB Output is correct
17 Runtime error 407 ms 218496 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 78632 KB Output is correct
2 Correct 17 ms 78684 KB Output is correct
3 Correct 16 ms 78672 KB Output is correct
4 Correct 16 ms 78672 KB Output is correct
5 Correct 17 ms 78672 KB Output is correct
6 Correct 16 ms 78672 KB Output is correct
7 Correct 21 ms 78672 KB Output is correct
8 Correct 15 ms 78644 KB Output is correct
9 Correct 15 ms 78692 KB Output is correct
10 Correct 17 ms 78648 KB Output is correct
11 Correct 16 ms 78652 KB Output is correct
12 Correct 104 ms 107280 KB Output is correct
13 Correct 16 ms 78672 KB Output is correct
14 Correct 17 ms 78672 KB Output is correct
15 Correct 17 ms 78672 KB Output is correct
16 Correct 17 ms 78648 KB Output is correct
17 Runtime error 407 ms 218496 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -