Real LAZER Video Solution

editorial
,
1

I hope people didn’t take my prank too seriously :sweat_smile:

Official editorial coming soon
Video link: LAZER Solution - CodeChef March Long Challenge 2020 - YouTube

14 Likes
2

can u explain the logic for break problem?

3

The half-complete editorial for BREAK has been posted. If you have any questions you can ask me for now.

4

Are there any links for similar questions?

5

Hmm, it’s basically any problem involving sweepline + data structures. An example is offline queries for number of points in a 2d range.

Actually, this problem basically reduces to queries for sum of point weights in a 2d range, if we create points with values -1 and 1 at the start and end of segments (as shown in the video).

1 Like
6

struct event {
int y, t, i;
bool operator<(const event &o) const {
return make_pair(y, t)<make_pair(o.y, o.t);
}
};
how this part of code EVENT helps??
and how imaginary line starts and go upto infinity, and what this events are actually doing like 1 ,3 ,2
if the imaginary line meets any query then how it is working to find it ?? why sorting is required ? A line segment has two y point out of that minimum is for adding line segment and when it reaches maximum it is removed?

7

The minimum point in a line segment is when we +1 to v and the maximum is when we -1 to v, right?

A certain event happens when the line reaches the y coordinate of the event.

9

for(++i; i<n; i+=i&-i)
in update function why are you not updating at i?

10

Why use of MO’s getting TLE?
first I will do coordinate compression on Y and after that
I am using MO’s for queries

and for update I am using lazy BIT

so time complexity will be O(Q∗sqrt(N)∗logN) here is my code can someone help me why I am getting TLE?

https://www.codechef.com/viewsolution/30520434

1 Like
11

Even I got TLE with Mo’s algorithm. Complexity is around O(10^8).

12
13

There are 5 test cases, if you calculate 510^5300*17 then it’s very big.

1 Like
14

How to solve if queries are online.

16

Will answer change if type of event is numbered differently? Eg. 1 for query, 2 for add, 3 for delete?

17

You can try submitting it

2 Likes
18

Why am I getting TLE while submitting even though I have used exactly same code as provided in the video explanation.

    #include<bits/stdc++.h>
    using namespace std;
    const int mxn = 1e5;

    int a[mxn], ql[mxn], qr[mxn], ft[mxn], ans[mxn];
    long int qy[mxn];

    struct event {
    	int y, t, i;
    	bool operator<(const event &o) const {
    		//compare by value of y then by t
    		return make_pair(y, t)<make_pair(o.y, o.t);
    	}
    };

    int sum(int x){
        int r = 0;
        for(int i = 0; i < x; i++)
            r += ft[i];
        return r;
    }

void solve(){

    int n, q;
    scanf("%d %d", &n, &q);
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for(int i = 0; i < q; i++){
        scanf("%d %d %d", &ql[i], &qr[i], &qy[i]);
        ql[i]--;
        qr[i]--;
    }
    
    vector<event> ve;
    for(int i = 0; i + 1 < n; i++){
        ve.push_back({min(a[i], a[i + 1]), 1, i});
        ve.push_back({max(a[i], a[i + 1]), 3, i});
    }

    for(int i = 0; i < q; i++)
        ve.push_back({qy[i], 2, i});
    
    sort(ve.begin(), ve.end());
    for(event e : ve){
        if(e.t == 1)
            ft[e.i]++;
        else if(e.t == 2)
            ans[e.i] = sum(qr[e.i]) - sum(ql[e.i]);
        else
            ft[e.i]--;
    }

    for(int i = 0; i < q; i++){
        printf("%d \n", ans[i]);
    }
}

int main(){

    int t;
    scanf("%d", &t);
    while(t--){
        solve();
    }
}
19

https://www.codechef.com/viewsolution/30606973

Coded this based on the video solution. Can somebody point out where i am going wrong here. Also when querrying the array for sum should’nt we subtract one from the left index to make query inclusive of both left and right indices.

Thank you.