Submission #513152

#	Time	Username	Problem	Language	Result	Execution time	Memory
513152		79brue	Worst Reporter 2 (JOI16_worst_reporter2)	C++14	60 / 100	2087 ms	13664 KiB

worst_reporter2

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct dat{
    int x, y; bool d; /// 0: 진입
    dat(){}
    dat(int x, int y, bool d): x(x), y(y), d(d){}
    bool operator<(const dat &r)const{
        if(y != r.y) return y < r.y;
        return d < r.d;
    }
};

int n;
vector<dat> vec;
int cnt[200002];
int ans;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        vec.push_back(dat(x, y, 0));
    }
    for(int i=1; i<=n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        vec.push_back(dat(x, y, 1));
    }
    sort(vec.begin(), vec.end());

    for(int i=0; i<n+n; i++){
        if(vec[i].d == 0){
            cnt[vec[i].x]++;
            continue;
        }
        if(cnt[vec[i].x]){
            cnt[vec[i].x]--;
            continue;
        }
        ans++;

        vector<int> problem (n+5, 1e9);
        vector<int> sum (n+5, 0);
        for(int j=1; j<=n; j++) sum[j] = cnt[j] - 1;
        for(int j=i; j<n+n; j++){
            if(vec[j].d == 0) sum[vec[j].x]++;
            else if(sum[vec[j].x]) sum[vec[j].x]--;
            else problem[vec[j].x] = min(problem[vec[j].x], j);
        }
        int key = 0, val = -1;
        for(int j=1; j<=n; j++) if(cnt[j] && problem[j] > val) val = problem[j], key = j;

        cnt[key]--;
    }
    printf("%d", ans);
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
worst_reporter2.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
worst_reporter2.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40