結果
問題 | No.2154 あさかつの参加人数 |
ユーザー | ZOI-dayo |
提出日時 | 2023-10-18 15:40:44 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 763 ms / 2,000 ms |
コード長 | 8,622 bytes |
コンパイル時間 | 2,910 ms |
コンパイル使用メモリ | 247,684 KB |
実行使用メモリ | 11,084 KB |
最終ジャッジ日時 | 2024-09-18 11:47:53 |
合計ジャッジ時間 | 19,288 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 729 ms
11,008 KB |
testcase_01 | AC | 697 ms
11,008 KB |
testcase_02 | AC | 739 ms
11,008 KB |
testcase_03 | AC | 743 ms
11,084 KB |
testcase_04 | AC | 763 ms
11,008 KB |
testcase_05 | AC | 58 ms
5,376 KB |
testcase_06 | AC | 345 ms
6,528 KB |
testcase_07 | AC | 434 ms
8,192 KB |
testcase_08 | AC | 514 ms
8,960 KB |
testcase_09 | AC | 338 ms
7,296 KB |
testcase_10 | AC | 399 ms
7,680 KB |
testcase_11 | AC | 658 ms
10,240 KB |
testcase_12 | AC | 436 ms
7,680 KB |
testcase_13 | AC | 175 ms
5,376 KB |
testcase_14 | AC | 417 ms
7,552 KB |
testcase_15 | AC | 468 ms
8,704 KB |
testcase_16 | AC | 500 ms
8,448 KB |
testcase_17 | AC | 445 ms
7,424 KB |
testcase_18 | AC | 543 ms
8,704 KB |
testcase_19 | AC | 72 ms
5,376 KB |
testcase_20 | AC | 558 ms
9,072 KB |
testcase_21 | AC | 308 ms
6,912 KB |
testcase_22 | AC | 604 ms
10,496 KB |
testcase_23 | AC | 552 ms
8,984 KB |
testcase_24 | AC | 669 ms
10,076 KB |
ソースコード
#line 1 "test/yukicoder/2154__imos.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/2154" #line 2 "common/template.hpp" #line 2 "common/alias.hpp" #include <bits/stdc++.h> // #include <gmpxx.h> // #include <boost/multiprecision/cpp_int.hpp> #line 2 "common/print.hpp" #line 4 "common/print.hpp" using namespace std; // --------------- // ----- TOC ----- template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p); template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p); template <typename T> ostream &operator<<(ostream &os, const vector<T> &v); template <typename T> ostream &operator<<(ostream &os, const vector<vector<T>> &v); template <typename T> ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v); template <typename T> istream &operator>>(istream &is, vector<T> &v); template <typename T, typename S> ostream &operator<<(ostream &os, const map<T, S> &mp); template <typename T> ostream &operator<<(ostream &os, const set<T> &st); template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st); template <typename T> ostream &operator<<(ostream &os, queue<T> q); template <typename T> ostream &operator<<(ostream &os, deque<T> q); template <typename T> ostream &operator<<(ostream &os, stack<T> st); template <class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq); // --- END TOC --- // --------------- template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << "(" << p.first << "," << p.second << ")"; return os; } template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) { os << "["; for (int i = 0; i < (int)v.size(); i++) { os << v[i] << (i + 1 != (int)v.size() ? ", " : "]"); } return os; } template <typename T> ostream &operator<<(ostream &os, const vector<vector<T>> &v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i] << endl; } return os; } template <typename T> ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v) { for (int i = 0; i < (int)v.size(); i++) { os << "i = " << i << endl; os << v[i]; } return os; } template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; } template <typename T, typename S> ostream &operator<<(ostream &os, const map<T, S> &mp) { for (auto &[key, val] : mp) { os << key << ":" << val << " "; } return os; } template <typename T> ostream &operator<<(ostream &os, const set<T> &st) { os << "{"; auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? ", " : "}"); itr++; } return os; } template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; } template <typename T> ostream &operator<<(ostream &os, queue<T> q) { while (q.size()) { os << q.front() << " "; q.pop(); } return os; } template <typename T> ostream &operator<<(ostream &os, deque<T> q) { while (q.size()) { os << q.front() << " "; q.pop_front(); } return os; } template <typename T> ostream &operator<<(ostream &os, stack<T> st) { while (st.size()) { os << st.top() << " "; st.pop(); } return os; } template <class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq) { while (pq.size()) { os << pq.top() << " "; pq.pop(); } return os; } #line 8 "common/alias.hpp" using namespace std; // using namespace boost::multiprecision; // --- 型エイリアス --- using ll = long long; template <typename T> using vec = vector<T>; template <typename T> using vvec = vector<vector<T>>; template <typename T> using p_queue = priority_queue<T>; template <typename T> using rp_queue = priority_queue<T, vec<T>, greater<T>>; // --- 黒魔術 --- #define int ll // --- 制御マクロ --- #define rep(i, n) for (ll i = 0; i < n; ++i) #define all(v) begin(v), end(v) #define BIT(n) (1LL << (n)) #define MAX(type) numeric_limits<type>::max() #define MIN(type) numeric_limits<type>::min() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define pb push_back #define mp make_pair #define fir first #define sec second // --- 定数 --- constexpr ll INF = 1LL << 60; #line 2 "common/debug.hpp" #line 4 "common/debug.hpp" // --- デバッグ --- #ifndef ONLINE_JUDGE // #define printd(x) cerr << #x << ": " << x << endl; const string _TERM_ESC = "\033"; const string _TERM_BOLD = _TERM_ESC + "[1m"; const string _TERM_DECO_RESET = _TERM_ESC + "[0m"; const string _TERM_FORE_RED = _TERM_ESC + "[31m"; const string _TERM_FORE_RESET = _TERM_ESC + "[39m"; const string _TERM_BACK_RED = _TERM_ESC + "[41m"; const string _TERM_BACK_RESET = _TERM_ESC + "[49m"; #define line_debug() cerr << "line: " << __LINE__ << endl; #define coutd(x) cerr << "[debug] " << x; #define printd(x) \ cerr << _TERM_BOLD << _TERM_BACK_RED << "[debug] " << #x << " = " << x \ << _TERM_BACK_RESET << _TERM_DECO_RESET << endl; #else #define line_debug() ; #define coutd(x) ; #define printd(x) ; #endif #line 2 "common/util.hpp" #line 4 "common/util.hpp" // --- Utils --- // 二分探索 template <typename T> inline T bin_search(T ok, T ng, const function<bool(T)> is_ok) { assert(is_ok(ok) && !is_ok(ng)); assert(ok < ng); while (abs(ok - ng) > 1) { T mid = (ok + ng) / 2; if (is_ok(mid)) ok = mid; else ng = mid; } return ok; } // 合計値を求める ll sum(const vec<ll> &v) { return accumulate(all(v), 0LL); } // 可変引数min template <class... T> auto min(T... a) { return min(initializer_list<common_type_t<T...>>{a...}); } // 可変引数max template <class... T> auto max(T... a) { return max(initializer_list<common_type_t<T...>>{a...}); } template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } // 3項間不等式 // 広義単調増加 bool is_increasing(int x, int y, int z) { return x <= y && y <= z; } // 半開区間[x, z)にyが含まれるか? bool is_contained(int x, int y, int z) { return x <= y && y < z; } // 頂点(x, y)が範囲に含まれるか bool is_contained(int H, int W, int x, int y) { return is_contained(0, x, H) && is_contained(0, y, W); } // rootに対し、aとbが同じ側にあるか (=は含まない) bool is_same_side(int root, int a, int b) { return (root < a) == (root < b); } // vector継承にする? template <typename T> struct vec_accumulate : vec<T> { vec<T> data; explicit vec_accumulate(vec<T> &v) : data(v.size()) { assert(v.size() > 0); data[0] = v[0]; for (int i = 1; i < v.size(); ++i) data[i] = data[i - 1] + v[i]; } T &operator[](int i) { assert(is_contained(-1, i, data.size())); if (i == -1) return T(); return data[i]; } }; void io_setup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << std::fixed << std::setprecision(15); } #line 2 "datastructure/imos.hpp" #line 4 "datastructure/imos.hpp" template<typename T> struct imos{ private: int _n; vec<T> _data, _raw; bool _is_build = false; public: imos(int n) : _n(n), _data(_n+1, 0), _raw(_n, 0) {} imos(vec<T> src) : _n(src.size()), _data(_n+1, 0), _raw(_n, 0) { rep(i, _n) add(i, src[i]); } inline void add(int l, int r, T x) { assert(l < r); assert(0 <= l && r <= _n); _is_build = false; _data[l] += x; _data[r] -= x; } inline void add(int i, T x) { assert(0 <= i && i < _n); _is_build = false; add(i, i+1, x); } inline void build() { _raw[0] = _data[0]; for(int i=1; i<_n; i++) _raw[i] = _raw[i-1] + _data[i]; _is_build = true; } inline T get(int i) { assert(0 <= i && i < _n); if (!_is_build) build(); return _raw[i]; } }; #line 5 "test/yukicoder/2154__imos.test.cpp" signed main() { io_setup(); int N, M; cin >> N >> M; imos<ll> imos(N); rep(i, M) { int l, r; cin >> l >> r; imos.add(N-l, N-r+1, 1); } imos.build(); rep(i, N) { cout << imos.get(i) << endl; } }