thảo luận Leetcode contest, đường tới Guardian

thangkc89 · 8/12/24

bài 4 cắm đầu sweep line hoá ra sai :too_sad:

chắc phải dùng segment tree 2D hay gì đó để count số lượng point trong rec nhanh

freedom.9 · 8/12/24

Nay ko làm, may quá chắc ko lại 3Q gang rồi =((

nahnahinin · 8/12/24

thangkc89 đã nói:
bài 4 cắm đầu sweep line hoá ra sai chắc phải dùng segment tree 2D hay gì đó để count số lượng point trong rec nhanh

sweep line x rồi count y bằng ordered_multiset

C++:

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
class Solution {
public:
    long long maxRectangleArea(vector<int>& xCoord, vector<int>& yCoord) {
        int n = xCoord.size();
        vector<pair<int, int>> points(n);
       
        for (int i = 0; i < n; i++) {
            points[i] = {xCoord[i], yCoord[i]};
        }
        sort(points.begin(), points.end());

        map<int, vector<int>> x_to_y;
        for (auto p : points) {
            x_to_y[p.first].push_back(p.second);
        }
        for (auto& entry : x_to_y) {
            sort(entry.second.begin(), entry.second.end());
        }
        long long res = -1;
        map<string, int> y_sum;
        unordered_map<string,int>m;
        ordered_multiset s;
        for (auto& [x1, yList] : x_to_y) {
            int y_count = yList.size();
            for (int i = 1; i < y_count; ++i) {
                string z= to_string(yList[i])+","+to_string(yList[i-1]);
                string z1= to_string(x1)+" "+to_string(yList[i])+","+to_string(yList[i-1]);
                int le = s.order_of_key(yList[i-1]);
                int lee = s.order_of_key(yList[i] + 1);
                y_sum[z1]=lee-le;
                if(m.find(z)!=m.end()){
                    int u=m[z];
                    string z2=to_string(u)+" "+z;
                    // cout<<z1<<" "<<z2<<"\n";
                    // cout<<y_sum[z1]<<" "<<y_sum[z2]<<"\n";
                    if(y_sum[z1]-y_sum[z2]-2==0){
                        res = max(res, abs(static_cast<long long>(u - x1)) * abs(static_cast<long long>(yList[i] - yList[i - 1])));
                    }
                }
                m[z]=x1;
            }
           
            for (int i = 0; i < y_count; ++i) {
                s.insert(yList[i]);
            }      
        }

        return res == -1 ? -1 : res;
    }
};
©leetcode

thangkc89 · 8/12/24

nahnahinin đã nói:

sweep line x rồi count y bằng ordered_multiset

C++:

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
class Solution {
public:
    long long maxRectangleArea(vector<int>& xCoord, vector<int>& yCoord) {
        int n = xCoord.size();
        vector<pair<int, int>> points(n);
      
        for (int i = 0; i < n; i++) {
            points[i] = {xCoord[i], yCoord[i]};
        }
        sort(points.begin(), points.end());

        map<int, vector<int>> x_to_y;
        for (auto p : points) {
            x_to_y[p.first].push_back(p.second);
        }
        for (auto& entry : x_to_y) {
            sort(entry.second.begin(), entry.second.end());
        }
        long long res = -1;
        map<string, int> y_sum;
        unordered_map<string,int>m;
        ordered_multiset s;
        for (auto& [x1, yList] : x_to_y) {
            int y_count = yList.size();
            for (int i = 1; i < y_count; ++i) {
                string z= to_string(yList[i])+","+to_string(yList[i-1]);
                string z1= to_string(x1)+" "+to_string(yList[i])+","+to_string(yList[i-1]);
                int le = s.order_of_key(yList[i-1]);
                int lee = s.order_of_key(yList[i] + 1);
                y_sum[z1]=lee-le;
                if(m.find(z)!=m.end()){
                    int u=m[z];
                    string z2=to_string(u)+" "+z;
                    // cout<<z1<<" "<<z2<<"\n";
                    // cout<<y_sum[z1]<<" "<<y_sum[z2]<<"\n";
                    if(y_sum[z1]-y_sum[z2]-2==0){
                        res = max(res, abs(static_cast<long long>(u - x1)) * abs(static_cast<long long>(yList[i] - yList[i - 1])));
                    }
                }
                m[z]=x1;
            }
          
            for (int i = 0; i < y_count; ++i) {
                s.insert(yList[i]);
            }     
        }

        return res == -1 ? -1 : res;
    }
};
©leetcode

Bác khủng quá, multiset là cái gì nghe lạ quá, lại có cái mới phải học rồi :adore:

freedom.9 · 8/12/24

thangkc89 đã nói:
Bác khủng quá, multiset là cái gì nghe lạ quá, lại có cái mới phải học rồi

Khủng thật, xin giáo án luyện codeforces đi mai fence @nahnahinin :ah:

thangkc89 · 8/12/24

freedom.9 đã nói:
Nay ko làm, may quá chắc ko lại 3Q gang rồi

Làm 3Q nhanh cũng húp được mà :hungry:

Vượt mức 2k3 rồi, có nên dừng ở đây để tiếng thơm còn mãi hay làm tiếp có khi về lại 2k :adore:

freedom.9 · 8/12/24

thangkc89 đã nói:
Xem tệp đính kèm 2821319

Làm 3Q nhanh cũng húp được mà
Vượt mức 2k3 rồi, có nên dừng ở đây để tiếng thơm còn mãi hay làm tiếp có khi về lại 2k

Làm 3Q nhanh để húp mình cứ thấy nhục nhục, con mẹ húp 3Q 4 5 contest rồi chỉ thấy trình độ gõ bàn phím lên nhanh hơn =((

làm sao để lên level mới AK đây =((

nahnahinin · 8/12/24

C++ STL: Policy based data structures - Codeforces

Codeforces. Programming competitions and contests, programming community

codeforces.com

ordered_set đây mà các bác code py có sorted_dict/list mà học cái này làm gì :v
này cũng là set thường thôi, mà set thường bên c++ ko có đếm bao nhiều phần tử <= x (chỉ có đếm bằng o(n)) mới vẽ ra cái này

athxzz · 8/12/24

tầm con problem này là độ khó bao nhiêu bên CF thế các bác, thử 1 contest mà ngợp luôn Problem - C - Codeforces (https://codeforces.com/contest/2040/problem/C)

Tinh Hoa Đông Lào · 8/12/24

athxzz đã nói:
tầm con problem này là độ khó bao nhiêu bên CF thế các bác, thử 1 contest mà ngợp luôn Problem - C - Codeforces (https://codeforces.com/contest/2040/problem/C)

trông hard leetcode quá, hóng bác freedom 2Q gang :big_smile:

freedom.9 · 9/12/24

Tinh Hoa Đông Lào đã nói:
trông hard leetcode quá, hóng bác freedom 2Q gang

Hôm nay mình ngủ quên mẹ mất fen à nên ko thi =((

cả ngày hôm qua ngủ được có mấy tiếng nên sáng mở mắt đã thấy quá giờ thi.
Hay xin mod đổi tên topic thành Competitive programming cho ae luyện Leetcode + codeforces luôn nhỉ

LmaoSuVuong · 9/12/24

athxzz đã nói:
tầm con problem này là độ khó bao nhiêu bên CF thế các bác, thử 1 contest mà ngợp luôn Problem - C - Codeforces (https://codeforces.com/contest/2040/problem/C)

đọc tag câu nào cũng có math, làm leetcode thuần ngợp là rõ. bên CP giải thì nền toán cũng phải cứng đấy.

freedom.9 · 9/12/24

Toán thì ko ngán, học dần là được, mà xài python ngán quá TLE tùm lum, dfs cũng éo được toàn run time error nản thật. Giờ muốn luyện lại đi học lại c++ mệt vãi :canny:

via theNEXTvoz for iPhone

LmaoSuVuong · 9/12/24

freedom.9 đã nói:
Toán thì ko ngán, học dần là được, mà xài python ngán quá TLE tùm lum, dfs cũng éo được toàn run time error nản thật. Giờ muốn luyện lại đi học lại c++ mệt vãi

via theNEXTvoz for iPhone

bác đang làm c# thì xài c# đi :angry:

Tinh Hoa Đông Lào · 9/12/24

freedom.9 đã nói:
Toán thì ko ngán, học dần là được, mà xài python ngán quá TLE tùm lum, dfs cũng éo được toàn run time error nản thật. Giờ muốn luyện lại đi học lại c++ mệt vãi

via theNEXTvoz for iPhone

Lên 3k leetcode, 2k2 CF xong học C++ cũng được bác :big_smile:

, ô nhà vật lý vẫn python

seastar · 9/12/24

freedom.9 đã nói:
Toán thì ko ngán, học dần là được, mà xài python ngán quá TLE tùm lum, dfs cũng éo được toàn run time error nản thật. Giờ muốn luyện lại đi học lại c++ mệt vãi

via theNEXTvoz for iPhone

Tinh Hoa Đông Lào đã nói:
Lên 3k leetcode, 2k2 CF xong học C++ cũng được bác , ô nhà vật lý vẫn python

Xem tệp đính kèm 2823114

Ngôn ngữ không phế, người dùng ngôn ngữ không đúng mới phế, :doubt:

Tinh Hoa Đông Lào · 9/12/24

seastar đã nói:
Ngôn ngữ không phế, người dùng ngôn ngữ không đúng mới phế,

từ lúc đi làm đến h chưa bao giờ code ngôn ngữ có dấu chấm phẩy, giờ bảo chuyển sang cứ khó chịu sao ấy bác ạ :sweat:

lilleboybk · 9/12/24

seastar đã nói:
Ngôn ngữ không phế, người dùng ngôn ngữ không đúng mới phế,

Typescript cho thuật toán em thấy phế ấy bác, ko có nhiều lib sẵn như heap, order set,...Năm sau chắc em chuyển sang C++ cho giống số đông.

Tinh Hoa Đông Lào · 9/12/24

nahnahinin đã nói:
C++ STL: Policy based data structures - Codeforces

Codeforces. Programming competitions and contests, programming community

codeforces.com

ordered_set đây mà các bác code py có sorted_dict/list mà học cái này làm gì :v
này cũng là set thường thôi, mà set thường bên c++ ko có đếm bao nhiều phần tử <= x (chỉ có đếm bằng o(n)) mới vẽ ra cái này

C++ trên leetcode dùng hàm gì để in ra debug vậy bác, hàm print của python nó chơi được hết loại data mà C++ có vẻ ko có :sweat:

freedom.9 · 9/12/24

Tinh Hoa Đông Lào đã nói:
Lên 3k leetcode, 2k2 CF xong học C++ cũng được bác , ô nhà vật lý vẫn python

Xem tệp đính kèm 2823114

Fen xài Python rồi sẽ hiểu, khó chịu vl.
Lời khuyên tụi nó là ko xài dfs với topdown Dp

via theNEXTvoz for iPhone

thảo luận Leetcode contest, đường tới Guardian

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Member

Junior Member

Senior Member

Junior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này