Submission #237711

#	Time	Username	Problem	Language	Result	Execution time	Memory
237711		Half	Lasers (NOI19_lasers)	C++14	45 / 100	418 ms	6152 KiB

lasers

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pi;
typedef long long ll;

#define loop(i,a,b) for (int i = a; i <= b; i++)

#define INF ((unsigned) ~0)
#define F first
#define S second
#define PB push_back
#define MP make_pair

const int MXL = 1000000000;
int L, R, sol;
set<pi> rgs;

void rUp(int l, int r){
    if(r <= l)
        return;
    if(rgs.size() == 0){
        rgs.insert(MP(l, r));
        sol += r - l;
        return;
    }
    set<pi>::iterator it = rgs.upper_bound(MP(l, -1));
    pi pa, pb;
    if(it == rgs.end()){
        it--;
        pa = *it;
        sol += max(r - l - max(pa.S - l, 0), 0);
        if(pa.S >= l && pa.S < r){
            rgs.erase(pa);
            rgs.insert(MP(pa.F, r));
        }else if(pa.S < l){
            rgs.insert(MP(l, r));
        }
        return;
    }
    if(it == rgs.begin()){
        pb = *it;
        sol += max(r - l - max(r - pb.F, 0), 0);
        if(r >= pb.F && l < pb.F){
            rgs.erase(pb);
            rgs.insert(MP(l, pb.S));
            if(r > pb.S){
                rUp(pb.S, r);
            }
        }else if(r < pb.F){
            rgs.insert(MP(l, r));
        }
        return;
    }
    pa = *(--it);
    pb = *(++it);
    sol += max(r - l - max(pa.S - l, 0) - max(r - pb.F, 0), 0);
    if(pa.S >= l && r >= pb.F){
        rgs.erase(pa);
        rgs.erase(pb);
        rgs.insert(MP(pa.F, pb.S));
        if(r > pb.S){
            rUp(pb.S, r);
        }
    }else if(pa.S >= l && pa.S < r){
        rgs.erase(pa);
        rgs.insert(MP(pa.F, r));
    }else if(r >= pb.F && l < pb.F){
        rgs.erase(pb);
        rgs.insert(MP(l, pb.S));
        if(r > pb.S){
            rUp(pb.S, r);
        }
    }else if(l > pa.S && r < pb.F){
        rgs.insert(MP(l, r));
    }
    return;
}

int main(){
    sol = 0;
    cin >> L >> R;
    for(int k = 0; k < R; k++){
        int X, gp = L, sm = 0;
        cin >> X;
        int a[500000];
        for(int i = 0; i < X; i++){
            cin >> a[i];
            gp -= a[i];
        }
        for(int i = 0; i < X; i++){
            rUp(sm + gp, sm + a[i]);
            sm += a[i];
        }
        /*for(set<pi>::iterator it = rgs.begin(); it != rgs.end(); it++){
            cout << "\n" << it->F << " " << it->S << "\n\n";
        }*/
    }
    cout << sol << "\n";
}

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