Submission #544678

#	Time	Username	Problem	Language	Result	Execution time	Memory
544678		pokmui9909	곡선 자르기 (KOI17_cut)	C++17	100 / 100	247 ms	33580 KiB

cut

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second

int n;
vector<pair<int, int>> V;
pair<int, int> A[1000005];

signed main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n;
    for (int i = 0; i < n; i++) cin >> A[i].x >> A[i].y;
    rotate(A, min_element(A, A + n,
        [&](pair<int, int> a, pair<int, int> b) -> bool
        {
            if (a.y != b.y) return a.y < b.y;
            else return a.x < b.x;
        }), A + n);
    int flag = 0, idx = -1;
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (A[i].y > 0 && flag == 0) flag = 1, idx = A[i].x;
        if (flag == 1 && A[i].y < 0)
        {
            flag = 0;
            int a = idx, b = A[i].x;
            if (a > b) swap(a, b);
            cnt++;
            V.push_back({a, cnt});
            V.push_back({b, cnt});
        }
    }
    sort(V.begin(), V.end());
    stack<int> st;
    int ans1 = 0, ans2 = 0;
    for(int i = 0; i < V.size(); i++)
    {
       int x = V[i].second;
       if(st.empty()) st.push(x);
       else
       {
          if(st.top() != x) st.push(x);
          else
          {
             st.pop();
             if(st.empty()) ans1++;
             if(V[i].y == V[i - 1].y) ans2++;
          }
       }
    }
    cout << ans1 << ' ' << ans2;
}

Compilation message (stderr)

cut.cpp: In function 'int main()':
cut.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0; i < V.size(); i++)
      |                    ~~^~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 24 / 24
• Subtask 3: 65 / 65