LBC_2C - Trò chơi vòng kẹo

Xem dạng PDF
Gửi bài giải
Điểm: 1,50 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Tác giả:
wronganswer
Dạng bài

Sau những kỳ thi căng thẳng Quỳnh quyết định về quê để xả hơi sau những chuỗi ngày chinh chiến. Về quê cô ấy thích chơi các trò chơi với những đứa trẻ trong xóm. Trò chơi ấy như sau:

  • Quỳnh có một vòng tròn gồm ~N~ ô trống.
  • Có ~M~ lượt, mỗi lượt Quỳnh sẽ nhờ "lũ trẻ trong xóm" chọn giúp cô ấy 2 số ~L, R~.
  • Với 2 số ~L, R~, Quỳnh sẽ thả vào mỗi ô trống 1 viên sỏi theo chiều kim đồng hồ từ ô thứ ~L~ tới ~R~.

Trò chơi kết thúc sau ~M~ lượt và có người đoán được số sỏi nhiều nhất có trong 1 hộp.

Để giành được phần quà là một chiếc kẹo nhỏ xinh do Quỳnh làm. Bạn hãy tính xem số sỏi nhiều nhất có trong 1 hộp.

Input

  • Dòng đầu tiên gồm 2 số nguyên dương ~N, M~ được phân cách nhau bởi dấu cách ~(1 \leq N, M \leq 10^6)~.
  • ~M~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ~L, R~ được phân tách nhau bởi dấu cách ~(1 \leq L, R \leq N)~.

Output

  • Gồm một dòng chứa 1 số nguyên lần lượt là số sỏi nhiều nhất có trong 1 hộp sau ~M~ lượt.

Sample

Input #1
5 4
1 5
2 3
4 1
4 5
Output #1
3
Input #2
7 5
2 4
3 2
7 7
4 7
7 1
Output #2
4
Input #3
5 2
1 5
4 2
Output #3
2

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    AnDev2009  đã bình luận lúc 17, Tháng 4, 2024, 12:38

    Hello


  • -1
    vuminhkhang  đã bình luận lúc 15, Tháng 4, 2024, 14:52

    include<bits/stdc++.h>

    using namespace std;

    struct Point { long start; long end; };

    vector<Point> A;

    void Solve(long n, long m) { long count = 0; long max = -1;

    for (long i = 1; i <= n; i++) {
    if(max == m) break;
    for(long j = 0; j < A.size(); j++){
        long temp = m - max;
        if(j+1-count > temp && max != -1) break;
        if (A[j].start <= A[j].end && i >= A[j].start && i <= A[j].end) {
            count++;
        }
        else if (A[j].start > A[j].end && (i >= A[j].start || i <= A[j].end)) {
            count++;
        }
   }
   if(max < count ) max = count;
   count = 0;
}

cout << max;

    }

    int main() { long n, m; Point p; cin >> n >> m;

    for (long i = 0; i < m; i++) {
    cin >> p.start >> p.end;
    A.push_back(p);
}

Solve(n,m);

    }


  • -1
    vuminhkhang  đã bình luận lúc 15, Tháng 4, 2024, 14:52

    include<bits/stdc++.h>

    using namespace std;

    struct Point { long start; long end; };

    vector<Point> A;

    void Solve(long n, long m) { long count = 0; long max = -1;

    for (long i = 1; i <= n; i++) {
    if(max == m) break;
    for(long j = 0; j < A.size(); j++){
        long temp = m - max;
        if(j+1-count > temp && max != -1) break;
        if (A[j].start <= A[j].end && i >= A[j].start && i <= A[j].end) {
            count++;
        }
        else if (A[j].start > A[j].end && (i >= A[j].start || i <= A[j].end)) {
            count++;
        }
   }
   if(max < count ) max = count;
   count = 0;
}

cout << max;

    }

    int main() { long n, m; Point p; cin >> n >> m;

    for (long i = 0; i < m; i++) {
    cin >> p.start >> p.end;
    A.push_back(p);
}

Solve(n,m);

    }