Submission #523958


Source Code Expand

Copy
#define _CRT_SECURE_NO_WARNINGS
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// #define int ll
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
#define all(c) begin(c), end(c)
#define range(i,a,b) for(ll i=a; i<ll(b); i++)
#define rep(i,b) range(i,0,b)
#define rangei(i,a,b) for(ll a=a;i<=ll(b);i++)
#define repi(i,b) rangei(i,1,b)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
template<class T> ostream & operator << (ostream &os, vector<T> const &);
template<int n, class...T>
typename enable_if<(n>=sizeof...(T))>::type
_ot(ostream &, tuple<T...> const &){}
template<int n, class...T>
typename enable_if<(n< sizeof...(T))>::type
_ot(ostream &os, tuple<T...> const &t){
    os << (n==0?"":" ") << get<n>(t); _ot<n+1>(os, t);
}
template<class...T>
ostream & operator << (ostream &os, tuple<T...> const &t){
    _ot<0>(os, t); return os;
}
template<class T, class U>
ostream & operator<<(ostream &os, pair<T,U> const &p){
    return os << "(" << p.first << ", " << p.second << ") ";
}
template<class T>
ostream & operator<<(ostream &os, vector<T> const &v){
    rep(i,v.size()) os << v[i] << (i+1==(int)v.size()?"":" "); return os;
}
#ifdef DEBUG
#define dump(...) (cerr << #__VA_ARGS__ << " = " << mt(__VA_ARGS__) \
                   << " [" << __LINE__ << "]" << endl)
#else
#define dump(...)
#endif
void fastios(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // #define endl '\n'
}
template<class T>
size_t uniq(vector<T> &v){
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    return v.size();
}
template<class T>
size_t uniq(T *l, size_t n){
    sort(l,l+n);
    return unique(l,l+n) - l;
}
#define mems(arr,val) memset(arr,val,sizeof(arr));
int const mod = 1000000007;
int const inf = numeric_limits<int>::max()/8;

int n;
int m;
vi s, t;

vi solve(){
    vector<int> c(n+1);
    vector<vector<pair<int,int>>> events(n+1); // pos -> on/off s
    rep(i,m){
        events[s[i]].eb(i,+1);
        events[t[i]+1].eb(i,-1);
        c[s[i]]++;
        c[t[i]+1]--;
    }
    rep(i,n){
        c[i+1] += c[i];
    }
    // dump(c);
    set<int> bad;
    set<int> cur;
    rep(i,n){
        // dump(i,c[i]);
        // dump(vector<int>(all(cur)));
        for(auto & e : events[i]){
            if(e.second == +1) cur.insert(e.first);
            if(e.second == -1) cur.erase(e.first);
        }
        assert(c[i] == cur.size());
        if(c[i] == 1){
            bad.emplace(*cur.begin());
        }
    }
    //cout << m - bad.size() << "\n";
    vi ans;
    rep(i,m){
        if(bad.count(i)==0) ans.pb(i+1);
    }
    return ans;
}

signed main(){
    fastios();
    while(cin >> n){
        cin >> m;
        s.resize(m);
        t.resize(m);
        rep(i,m) cin >> s[i] >> t[i], s[i]--, t[i]--;
        auto ans = solve();
        dump(ans);
        cout << ans.size() << "\n";
        rep(i,ans.size()){
            cout << ans[i] << "\n";
        }
    }
}

Submission Info

Submission Time
Task B - ドキドキデート大作戦高橋君
User tubo28
Language C++11 (GCC 4.9.2)
Score 100
Code Size 3148 Byte
Status
Exec Time 264 ms
Memory 20640 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
Subtask1 30 / 30 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
All 70 / 70 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt 25 ms 928 KB
subtask0_sample_02.txt 23 ms 924 KB
subtask0_sample_03.txt 23 ms 920 KB
subtask1_01.txt 230 ms 17572 KB
subtask1_02.txt 154 ms 12696 KB
subtask1_03.txt 165 ms 16416 KB
subtask1_04.txt 180 ms 12064 KB
subtask1_05.txt 182 ms 12064 KB
subtask1_06.txt 24 ms 800 KB
subtask1_07.txt 23 ms 924 KB
subtask1_08.txt 25 ms 736 KB
subtask1_09.txt 28 ms 928 KB
subtask2_01.txt 181 ms 16956 KB
subtask2_02.txt 219 ms 20640 KB
subtask2_03.txt 23 ms 920 KB
subtask2_04.txt 26 ms 796 KB
subtask2_05.txt 25 ms 732 KB
subtask2_06.txt 27 ms 804 KB
subtask2_07.txt 26 ms 928 KB
subtask2_08.txt 264 ms 13972 KB