結果
問題 | No.2338 Range AtCoder Query |
ユーザー |
![]() |
提出日時 | 2023-06-02 23:56:28 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 8,540 bytes |
コンパイル時間 | 9,581 ms |
コンパイル使用メモリ | 542,024 KB |
実行使用メモリ | 153,504 KB |
最終ジャッジ日時 | 2024-12-29 00:44:04 |
合計ジャッジ時間 | 105,028 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 17 TLE * 17 |
ソースコード
/*このコード、と~おれ!Be accepted!∧_∧(。・ω・。)つ━☆・*。⊂ ノ ・゜+.しーJ °。+ *´¨).· ´¸.·*´¨) ¸.·*¨)(¸.·´ (¸.·'* ☆*/#include <cstdio>#include <algorithm>#include <string>#include <cmath>#include <cstring>#include <vector>#include <numeric>#include <iostream>#include <random>#include <map>#include <unordered_map>#include <queue>#include <regex>#include <functional>#include <complex>#include <list>#include <cassert>#include <iomanip>#include <set>#include <stack>#include <bitset>#include <array>#include <chrono>#include <limits>//#pragma GCC target("arch=skylake-avx512")#pragma GCC target("avx2")//#pragma GCC optimize("O3")#pragma GCC optimize("Ofast")//#pragma GCC target("sse4")#pragma GCC optimize("unroll-loops")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#define repeat(i, n, m) for(int i = n; i < (m); ++i)#define rep(i, n) for(int i = 0; i < (n); ++i)#define printynl(a) printf(a ? "yes\n" : "no\n")#define printyn(a) printf(a ? "Yes\n" : "No\n")#define printYN(a) printf(a ? "YES\n" : "NO\n")#define printim(a) printf(a ? "possible\n" : "imposible\n")#define printdb(a) printf("%.50lf\n", a)#define printLdb(a) printf("%.50Lf\n", a)#define printdbd(a) printf("%.16lf\n", a)#define prints(s) printf("%s\n", s.c_str())#define all(x) (x).begin(), (x).end()#define deg_to_rad(deg) (((deg)/360.0L)*2.0L*PI)#define rad_to_deg(rad) (((rad)/2.0L/PI)*360.0L)#define Please return#define AC 0#define manhattan_dist(a, b, c, d) (abs(a - c) + abs(b - d))using ll = long long;using ull = unsigned long long;constexpr int INF = 1073741823;constexpr int MINF = -1073741823;constexpr ll LINF = ll(4661686018427387903);constexpr ll MOD = 1e9 + 7;constexpr ll mod = 998244353;constexpr long double eps = 1e-14;const long double PI = acosl(-1.0L);using namespace std;void scans(string& str) {char c;str = "";scanf("%c", &c);if (c == '\n')scanf("%c", &c);while (c != '\n' && c != -1 && c != ' ') {str += c;scanf("%c", &c);}}void scanc(char& str) {char c;scanf("%c", &c);if (c == -1)return;while (c == '\n') {scanf("%c", &c);}str = c;}double acot(double x) {return PI / 2 - atan(x);}ll LSB(ll n) { return (n & (-n)); }template<typename T>inline T chmin(T& a, const T& b) {if (a > b)a = b;return a;}template<typename T>inline T chmax(T& a, const T& b) {if (a < b)a = b;return a;}//cpp_int#if __has_include(<boost/multiprecision/cpp_int.hpp>)#include <boost/multiprecision/cpp_int.hpp>#include <boost/multiprecision/cpp_dec_float.hpp>using namespace boost::multiprecision;#elseusing cpp_int = ll;#endif//atcoder library#if __has_include(<atcoder/all>)#include <atcoder/all>//using namespace atcoder;#endif/*random_device seed_gen;mt19937 engine(seed_gen());uniform_int_distribution dist(1, 100);*//*----------------------------------------------------------------------------------*//** @title Mo's Algorithm* @docs kyopro/docs/mo.md*/template<typename ADD_LEFT, typename DEL_LEFT, typename REM, typename ADD_RIGHT = ADD_LEFT, typename DEL_RIGHT = DEL_LEFT, typename T = int>struct mo {int sqn, q, l, r, p;T ret;vector<tuple<int, int, int>> query;vector<T> ans;mo(const int& n, const int& q) : sqn((int)std::sqrt(n)), q(q), l(0), r(0), p(0), ret(T({ 0, 0 })), query(q), ans(q) {}inline void insert(const int& l, const int& r) {query[p] = { l, r, p };++p;}inline void read(const bool& oneindexed) {for (auto& [left, right, idx] : query) {scanf("%d%d", &left, &right);if (oneindexed)--left;idx = p++;}}void build() {sort(all(query), [&](const tuple<int, int, int>& a, const tuple<int, int, int>& b) {if (get<0>(a) / sqn != get<0>(b) / sqn)return get<0>(a) < get<0>(b);return get<1>(a) < get<1>(b);});}void run(const ADD_LEFT& add_left, const ADD_RIGHT& add_right, const DEL_LEFT& del_left, const DEL_RIGHT& del_right, const REM& rem) {for (const auto& [ql, qr, qo] : query) {while (l > ql)add_left(--l, ret);while (r < qr)add_right(r++, ret);while (l < ql)del_left(l++, ret);while (r > qr)del_right(--r, ret);rem(qo, ans, ret);}}void run(const ADD_LEFT& add, const DEL_LEFT& del, const REM& rem) {run(add, add, del, del, rem);}T operator [](const int& idx) {return ans[idx];}void allrun(const bool& oneindexed, const ADD_LEFT& add_left, const ADD_RIGHT& add_right, const DEL_LEFT& del_left, const DEL_RIGHT& del_right,const REM& rem) {read(oneindexed);build();run(add_left, add_right, del_left, del_right, rem);}void allrun(const bool& oneindexed, const ADD_LEFT& add, const DEL_LEFT& del, const REM& rem) {allrun(oneindexed, add, add, del, del, rem, rem);}};struct Node {Node* left, * right;ll v;Node() : left(nullptr), right(nullptr), v(0) {}};// Dynamic Segment Treeclass SegmentTree {Node* root;int n, n0;int query(int a, int b, Node* n, int l, int r) {if (a <= l && r <= b) {return n->v;}if (r <= a || b <= l) {return 0;}int lv = n->left ? query(a, b, n->left, l, (l + r) >> 1) : 0;int rv = n->right ? query(a, b, n->right, (l + r) >> 1, r) : 0;return (lv + rv) % MOD;}public:SegmentTree(int n) : n(n) {n0 = 1;while (n0 < n) n0 <<= 1;root = new Node();}~SegmentTree() {delete root; root = nullptr;}void update(int k, ll x) {Node* n = root;int l = 0, r = n0;n->v = (n->v + x);while (r - l > 1) {int m = (l + r) >> 1;if (k < m) {if (!n->left) n->left = new Node();n = n->left;r = m;}else {if (!n->right) n->right = new Node();n = n->right;l = m;}n->v = (n->v + x);}}int query(int a, int b) {return query(a, b, root, 0, n0);}int lquery(int b) {return query(0, b, root, 0, n0);}int rquery(int a) {return query(a, n0, root, 0, n0);}};//from: https://tjkendev.github.io/procon-library/cpp/range_query/dynamic_segment_tree.htmlint main() {int n, m, q;scanf("%d%d%d", &n, &m, &q);vector<pair<int, string>> a(n);SegmentTree *seg[200000];rep(i, m)seg[i] = new SegmentTree(n);rep(i, n) {scanf("%d%*c", &a[i].first);--a[i].first;scans(a[i].second);if (a[i].second == "WA")seg[a[i].first]->update(i, 1);}vector<int> wa(m);vector<set<int>> ac(m);int right = 0, left = 0;auto add_l = [&](const int& idx, pair<int, int>& ret) {if (a[idx].second == "AC") {if (ac[a[idx].first].empty())++ret.first;ac[a[idx].first].insert(idx);ret.second -= wa[a[idx].first];wa[a[idx].first] = 0;}else {if (not ac[a[idx].first].empty()) {++wa[a[idx].first];++ret.second;}}left = idx;};auto add_r = [&](const int& idx, pair<int, int>& ret) {if (a[idx].second == "AC") {if (ac[a[idx].first].empty()) {++ret.first;ret.second += seg[a[idx].first]->query(left, idx);wa[a[idx].first] += seg[a[idx].first]->query(left, idx);}ac[a[idx].first].insert(idx);}right = idx + 1;};auto del_l = [&](const int& idx, pair<int, int>& ret) {if (a[idx].second == "AC") {ac[a[idx].first].erase(idx);if (ac[a[idx].first].empty()) {--ret.first;ret.second -= wa[a[idx].first];wa[a[idx].first] = 0;}else {wa[a[idx].first] += seg[a[idx].first]->query(idx,ac[a[idx].first].empty() ? right : *ac[a[idx].first].begin());ret.second +=seg[a[idx].first]->query(idx,ac[a[idx].first].empty() ? right : *ac[a[idx].first].begin());}}else {if (not ac[a[idx].first].empty()) {--wa[a[idx].first];--ret.second;}}left = idx + 1;};auto del_r = [&](const int& idx, pair<int, int>& ret) {if (a[idx].second == "AC") {ac[a[idx].first].erase(idx);if (ac[a[idx].first].empty()) {--ret.first;ret.second -= wa[a[idx].first];wa[a[idx].first] = 0;}}right = idx;};vector<pair<int, int>> ans(q);auto rem = [](const int& idx, vector<pair<int, int>>& ans, const pair<int, int>& ret) {ans[idx] = ret;};mo<decltype(add_l), decltype(del_l), decltype(rem), decltype(add_r), decltype(del_r), pair<int, int>> mo(n, q);mo.allrun(true, add_l, add_r, del_l, del_r, rem);rep(i, q)printf("%d %d\n", mo[i].first, mo[i].second);Please AC;}