Real LAZER Video Solution

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

Official editorial coming soon
Video link: https://www.youtube.com/watch?v=Bp4nG6VZfWc

14 Likes

can u explain the logic for break problem?

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

Are there any links for similar questions?

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

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?

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.

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

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

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

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

1 Like

How to solve if queries are online.

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

You can try submitting it

2 Likes

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();
    }
}

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.