oj.uz

Submission #237711

# Submission time Handle Problem Language Result Execution time Memory
237711 2020-06-08T12:25:47 Z Half Lasers (NOI19_lasers) C++14
45 / 100
 418 ms 6152 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 256 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 5 ms 256 KB Output is correct
12 Correct 414 ms 6136 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 6 ms 384 KB Output is correct
17 Correct 418 ms 6152 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #5
0 / 22.0

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

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 5 ms 256 KB Output is correct
12 Correct 414 ms 6136 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 6 ms 384 KB Output is correct
17 Correct 418 ms 6152 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Incorrect 134 ms 5112 KB Output isn't correct
22 Halted 0 ms 0 KB -