Submission #1077463
Source Code Expand
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;
// cout vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
int len = v.size(); s << "\n";
for (int i = 0; i < len; ++i) {
s << v[i]; if (i < len - 1) s << "\t";
}
s << "\n"; return s;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
vi part(n+1, 0);
vi accum(n+1, 0);
vi s(m), t(m);
rep (i, m) {
scanf("%d %d", &s[i], &t[i]);
s[i] -= 1;
part[s[i]] += 1;
part[t[i]] -= 1;
}
accum[0] = part[0];
FOR (i, 1, n+1) {
accum[i] = accum[i-1] + part[i];
}
//assert(accum[n] == 0);
vi max_range(n+1);
rep (i, n) {
max_range[i] = i;
}
int current = 0;
rep (i, n+1) {
if (accum[i] < 2) {
max_range[current] = i;
current = i+1;
}
}
FOR (i, 1, n+1) {
max_range[i] = max(max_range[i-1], max_range[i]);
}
int ans = 0;
rep (i, m) {
if (max_range[s[i]] >= t[i]) {
ans += 1;
}
}
printf("%d\n", ans);
rep (i, m) {
if (max_range[s[i]] >= t[i]) {
printf("%d\n", i+1);
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
B - ドキドキデート大作戦高橋君 |
User |
tspcx |
Language |
C++14 (Clang++ 3.4) |
Score |
100 |
Code Size |
1986 Byte |
Status |
AC |
Exec Time |
83 ms |
Memory |
5028 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
30 / 30 |
70 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt |
Subtask1 |
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 |
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 |
AC |
20 ms |
868 KB |
subtask0_sample_02.txt |
AC |
16 ms |
800 KB |
subtask0_sample_03.txt |
AC |
17 ms |
928 KB |
subtask1_01.txt |
AC |
44 ms |
5028 KB |
subtask1_02.txt |
AC |
83 ms |
5020 KB |
subtask1_03.txt |
AC |
41 ms |
3872 KB |
subtask1_04.txt |
AC |
60 ms |
3224 KB |
subtask1_05.txt |
AC |
60 ms |
3232 KB |
subtask1_06.txt |
AC |
16 ms |
928 KB |
subtask1_07.txt |
AC |
17 ms |
800 KB |
subtask1_08.txt |
AC |
19 ms |
928 KB |
subtask1_09.txt |
AC |
17 ms |
792 KB |
subtask2_01.txt |
AC |
82 ms |
5020 KB |
subtask2_02.txt |
AC |
83 ms |
5028 KB |
subtask2_03.txt |
AC |
17 ms |
800 KB |
subtask2_04.txt |
AC |
17 ms |
800 KB |
subtask2_05.txt |
AC |
18 ms |
788 KB |
subtask2_06.txt |
AC |
20 ms |
732 KB |
subtask2_07.txt |
AC |
19 ms |
924 KB |
subtask2_08.txt |
AC |
82 ms |
3876 KB |