제출 #425462

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
425462		errorgorn	Lasers (NOI19_lasers)	C++17	87 / 100	587 ms	262148 KiB

lasers

#include <cstdio>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <cstring>
#include <utility>
using namespace std;
typedef pair<int,int> ii;
int l,r,total,run,lim;
bool st2=true; //its actually st1 and 2 but who cares
vector<int> v[500005];
vector<ii> range;
struct node{
    int s,e,m,len;
    bool blocked,split;
    node *l,*r;
    node(int _s,int _e){
        s=_s,e=_e,m=(s+e)>>1; //going to lazily build the ST
        blocked =false;
        split=false;
    }
    void update(int i,int j){
         if (i==s && j==e){
            blocked=true;
         }
         else{
            if (!split){
                split=true;
                l=new node(s,m);
                r=new node(m+1,e);
            }
            if (j<=m) l->update(i,j);
            else if (i>m) r->update(i,j);
            else l->update(i,m),r->update(m+1,j);
         }
    }
    int query(int i,int j){
        if (blocked) return e-s+1;
        else if (split) return l->query(i,m)+r->query(m+1,j);
        else return 0;
    }
}*root;
inline int read(){
    int x=0;
    char c=getchar_unlocked();
    while ('0'<=c && c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar_unlocked();
    }
    return x;
}
int main(){
    int a,b;
    //freopen("meow","r",stdin);
    l=read();
    r=read();
    root=new node(1,l);
    for (int x=0;x<r;x++){
        a=read();
        if (a!=1) st2=false;
        for (int y=0;y<a;y++){
            b=read();
            v[x].push_back(b);
        }
    }
    if (st2){
        int _max=0;
        for (int x=0;x<r;x++) _max=max(_max,v[x][0]);
        printf("%d\n",max(_max*2-l,0));
    }
    else {
        vector<ii>::iterator it;
        for (int x=0;x<r;x++){
            if (v[x].size()==0) continue;
            range.clear();
            total=0;
            run=0;
            for (vector<int>::iterator it=v[x].begin();it!=v[x].end();it++){
                total+=*it;
            }
            total=l-total;
            range.push_back(ii(1,total));
            for (vector<int>::iterator it=v[x].begin();it!=v[x].end();it++){
                run+=*it;
                range.push_back(ii(run+1,total));
            }
            int run=1;
            it=range.begin();
            while (run<=l){
                while (it!=range.end() && (*it).first<=run) run=max(run,(*it).first+(*it).second),it++;
                if (run<=l){
                    if (it!=range.end()) lim=( (*it).first);
                    else lim=l+1;
                    root->update(run,lim-1);
                    run=lim;
                }
            }
        }
        //for (auto i=s.begin();i!=s.end();i++) printf("%d ",*i);
        printf("%d\n",root->query(1,l));
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 22 / 22
• Subtask 6: 0 / 13