結果
問題 | No.230 Splarraay スプラレェーイ |
ユーザー | satanic |
提出日時 | 2016-08-26 18:50:53 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,425 bytes |
コンパイル時間 | 1,117 ms |
コンパイル使用メモリ | 126,216 KB |
実行使用メモリ | 12,316 KB |
最終ジャッジ日時 | 2024-04-25 18:01:45 |
合計ジャッジ時間 | 21,122 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,940 KB |
testcase_02 | AC | 1 ms
6,944 KB |
testcase_03 | AC | 1 ms
6,940 KB |
testcase_04 | AC | 1 ms
6,948 KB |
testcase_05 | AC | 3 ms
6,940 KB |
testcase_06 | AC | 61 ms
6,944 KB |
testcase_07 | AC | 3 ms
6,944 KB |
testcase_08 | AC | 3 ms
6,940 KB |
testcase_09 | AC | 4,825 ms
6,940 KB |
testcase_10 | AC | 68 ms
6,940 KB |
testcase_11 | AC | 3,023 ms
6,940 KB |
testcase_12 | AC | 4,884 ms
6,944 KB |
testcase_13 | AC | 204 ms
6,944 KB |
testcase_14 | WA | - |
testcase_15 | TLE | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
ソースコード
#include <algorithm> #include <bitset> #include <cassert> #include <complex> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <map> #include <memory> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <typeinfo> #include <utility> #include <vector> #include <array> #include <chrono> #include <random> #include <tuple> #include <unordered_map> #include <unordered_set> #define INIT std::ios::sync_with_stdio(false);std::cin.tie(0); #define VAR(type, ...)type __VA_ARGS__;Scan(__VA_ARGS__); template<typename T> void Scan(T& t) { std::cin >> t; } template<typename First, typename...Rest>void Scan(First& first, Rest&...rest) { std::cin >> first; Scan(rest...); } #define OUT(d) std::cout<<d; #define FOUT(n, d) std::cout<<std::fixed<<std::setprecision(n)<<d; #define SOUT(n, c, d) std::cout<<std::setw(n)<<std::setfill(c)<<d; #define SP std::cout<<" "; #define TAB std::cout<<"\t"; #define BR std::cout<<"\n"; #define FLUSH std::cout<<std::flush; #define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i; #define MAT(type, c, m, n) std::vector<std::vector<type>> c(m, std::vector<type>(n));for(auto& r:c)for(auto& i:r)std::cin>>i; #define ALL(a) (a).begin(),(a).end() #define FOR(i, a, b) for(int i=(a);i<(b);++i) #define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i) #define REP(i, n) for(int i=0;i<int(n);++i) #define RREP(i, n) for(int i=(n)-1;i>=0;--i) #define PAIR std::pair<int, int> #define IN(a, x, b) (a<=x && x<b) #define SHOW(d) {std::cout << #d << "\t:" << d << "\n";} #define SHOWVECTOR(v) {std::cout << #v << "\t:";for(const auto& i : v){std::cout << i << " ";}std::cout << "\n";} #define SHOWVECTOR2(v) {std::cout << #v << "\t:\n";for(const auto& i : v){for(const auto& j : i){std::cout << j << " ";}std::cout << "\n";}} #define SHOWPAIRVECTOR2(v) {std::cout << #v << "\t:\n";for(const auto& i : v){for(const auto& j : i){std::cout<<'('<<j.first<<", "<<j.second<<") ";}std::cout << "\n";}} #define SHOWPAIRVECTOR(v) {for(const auto& i:v){std::cout<<'('<<i.first<<", "<<i.second<<") ";}std::cout<<"\n";} #define CHECKTIME(state) {auto start=std::chrono::system_clock::now();state();auto end=std::chrono::system_clock::now();auto res=std::chrono::duration_cast<std::chrono::nanoseconds>(end-start).count();std::cerr<<"[Time:"<<res<<"ns ("<<res/(1.0e9)<<"s)]\n";} #define SHOWQUEUE(a) {std::queue<decltype(a.front())> tmp(a);std::cout << #a << "\t:";for(int i=0; i<static_cast<int>(a.size()); ++i){std::cout << tmp.front() << "\n";tmp.pop();}std::cout << "\n";} //#define int ll using ll = long long; using ull = unsigned long long; constexpr int INFINT = 1 << 30; constexpr ll INFLL = 1LL << 60; constexpr double EPS = 0.0000000001; constexpr int MOD = 1000000007; namespace std { PAIR operator+(const PAIR& l, const PAIR& r) { PAIR res(l); res.first += r.first; res.second += r.second; return res; } } class SegmentTree { private: int n; std::vector<PAIR> data; public: SegmentTree(int _n) :n(std::pow(2, std::ceil(std::log2(_n)))){ data.resize(2*n-1, PAIR(0, 0)); } // data[i] = xとする void update(int i, PAIR x) { i += n - 1; data[i] = x; while (i > 0) { i = (i - 1) / 2; data[i] = data[i * 2 + 1] + data[i * 2 + 2]; } } // 半開区間[a, b)について PAIR query(int a, int b) { return query(a, b, 0, 0, n); } PAIR query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return PAIR(0, 0); // ~~~~~~ if (a <= l && r <= b) return data[k]; else { PAIR vl = query(a, b, k * 2 + 1, l, (l + r) / 2); PAIR vr = query(a, b, k * 2 + 2, (l + r) / 2, r); return vl + vr; // ~~~~~~~~~~~~~~~~~ } } }; signed main() { VAR(int, n, Q); SegmentTree segtree(n); int a = 0, b = 0; REP(q, Q) { VAR(int, x, l, r); switch (x) { case 0: { PAIR t(segtree.query(l, r + 1)); if (t.first != t.second) { if (t.first > t.second) { a += t.first; } else { b += t.second; } } break; } case 1: { FOR(i, l, r + 1) { segtree.update(i, PAIR(1, 0)); } break; } case 2: { FOR(i, l, r + 1) { segtree.update(i, PAIR(0, 1)); } break; } } } PAIR tt = segtree.query(0, n); a += tt.first; b += tt.second; OUT(a)SP OUT(b)BR; return 0; }