oj.uz

Submission #1119831

# Submission time Handle Problem Language Result Execution time Memory
1119831 2024-11-27T13:42:02 Z Aviansh Lasers (NOI19_lasers) C++17
10 / 100
 137 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,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 52 ms 235088 KB Output is correct
2 Correct 46 ms 235224 KB Output is correct
3 Correct 43 ms 235260 KB Output is correct
4 Correct 56 ms 235156 KB Output is correct
5 Correct 51 ms 235240 KB Output is correct
6 Correct 46 ms 235104 KB Output is correct
7 Correct 54 ms 235088 KB Output is correct
8 Correct 44 ms 235080 KB Output is correct
9 Correct 58 ms 235076 KB Output is correct
10 Correct 55 ms 235224 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 235088 KB Output is correct
2 Correct 46 ms 235224 KB Output is correct
3 Correct 43 ms 235260 KB Output is correct
4 Correct 56 ms 235156 KB Output is correct
5 Correct 51 ms 235240 KB Output is correct
6 Correct 46 ms 235104 KB Output is correct
7 Correct 54 ms 235088 KB Output is correct
8 Correct 44 ms 235080 KB Output is correct
9 Correct 58 ms 235076 KB Output is correct
10 Correct 55 ms 235224 KB Output is correct
11 Correct 48 ms 235248 KB Output is correct
12 Runtime error 137 ms 262144 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 235180 KB Output is correct
2 Correct 48 ms 235088 KB Output is correct
3 Incorrect 50 ms 235164 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

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

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 235088 KB Output is correct
2 Correct 46 ms 235224 KB Output is correct
3 Correct 43 ms 235260 KB Output is correct
4 Correct 56 ms 235156 KB Output is correct
5 Correct 51 ms 235240 KB Output is correct
6 Correct 46 ms 235104 KB Output is correct
7 Correct 54 ms 235088 KB Output is correct
8 Correct 44 ms 235080 KB Output is correct
9 Correct 58 ms 235076 KB Output is correct
10 Correct 55 ms 235224 KB Output is correct
11 Correct 48 ms 235248 KB Output is correct
12 Runtime error 137 ms 262144 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -