結果
問題 | No.2421 entersys? |
ユーザー | bluebery1001 |
提出日時 | 2023-08-12 15:18:57 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 9,206 bytes |
コンパイル時間 | 8,634 ms |
コンパイル使用メモリ | 342,500 KB |
実行使用メモリ | 297,464 KB |
最終ジャッジ日時 | 2024-11-20 01:18:24 |
合計ジャッジ時間 | 53,721 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 5 ms
5,248 KB |
testcase_02 | AC | 11 ms
5,376 KB |
testcase_03 | AC | 3 ms
5,248 KB |
testcase_04 | AC | 5 ms
5,248 KB |
testcase_05 | AC | 8 ms
5,248 KB |
testcase_06 | AC | 8 ms
5,248 KB |
testcase_07 | AC | 8 ms
5,248 KB |
testcase_08 | AC | 10 ms
5,248 KB |
testcase_09 | AC | 14 ms
5,760 KB |
testcase_10 | AC | 7 ms
5,248 KB |
testcase_11 | AC | 2,392 ms
250,776 KB |
testcase_12 | AC | 2,447 ms
250,696 KB |
testcase_13 | AC | 2,412 ms
250,776 KB |
testcase_14 | AC | 2,386 ms
250,576 KB |
testcase_15 | AC | 2,427 ms
250,844 KB |
testcase_16 | AC | 2,475 ms
257,332 KB |
testcase_17 | AC | 2,450 ms
257,352 KB |
testcase_18 | AC | 2,448 ms
257,348 KB |
testcase_19 | AC | 2,471 ms
257,164 KB |
testcase_20 | AC | 2,473 ms
257,352 KB |
testcase_21 | AC | 2,169 ms
239,296 KB |
testcase_22 | AC | 2,070 ms
234,340 KB |
testcase_23 | TLE | - |
testcase_24 | TLE | - |
testcase_25 | TLE | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
ソースコード
using namespace std;#include<bits/stdc++.h>void _main();int main(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(0);_main();return 0;}#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")typedef long long ll;typedef long double ld;template<class ll>inline bool chmax(ll&a,ll b){if(a<b){a=b;return 1;}return 0;}template<class ll>inlinebool chmin(ll& a,ll b){if(a>b){a=b;return 1;}return 0;}#define rep1(a) for(int i = 0; i < a; i++)#define rep2(i, a) for(int i = 0; i < a; i++)#define rep3(i, a, b) for(int i = a; i < b; i++)#define rep4(i, a, b, c) for(int i = a; i < b; i += c)#define overload4(a, b, c, d, e, ...) e#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)#define ALL(x) std::begin(x),std::end(x)#define INF ((1LL<<62)-(1LL<<31))#define bit(x,i) (((x)>>(i))&1)#define fi first#define se second#define pb push_back#define Endl endl#define spa " "#define YesNo(x) cout<<(x?"Yes":"No")<<endl;inline void scan(){}template<class Head,class... Tail>inline void scan(Head&head,Tail&... tail){std::cin>>head;scan(tail...);}#define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__)#define STR(...) string __VA_ARGS__;scan(__VA_ARGS__)template<typename T>std::istream &operator>>(std::istream&is,std::vector<T>&v){for(T &in:v){is>>in;}return is;}template<typename T>std::ostream &operator<<(std::ostream&os,const std::vector<T>&v){for(auto it=std::begin(v);it!=std::end(v);){os<<*it<<((++it)!=std::end(v)?" ":"");}return os;}long double my_distance(long double xi,long double yi,long double xj,long double yj){return sqrt(abs((xi-xj)*(xi-xj))+abs((yi-yj)*(yi-yj)));}void print(){cout << '\n';}template<class T, class... Ts>void print(const T& a, const Ts&... b){cout << a;(cout << ... << (cout << ' ', b));cout << '\n';}template<class... T>constexpr auto min(T... a){return min(initializer_list<common_type_t<T...>>{a...});}template<class... T>constexpr auto max(T... a){return max(initializer_list<common_type_t<T...>>{a...});}//Union-Find from https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/vi((b%2==0?b-1:b)+2-(a%2==0?a+1:a))/2er/union-findclass UnionFind{public:UnionFind()=default;explicit UnionFind(size_t n):m_parentsOrSize(n, -1){}int find(int i){if(m_parentsOrSize[i]<0){return i;}return(m_parentsOrSize[i]=find(m_parentsOrSize[i]));}void merge(int a,int b){a=find(a);b=find(b);if(a!=b){if(-m_parentsOrSize[a]<-m_parentsOrSize[b]){std::swap(a,b);}m_parentsOrSize[a]+=m_parentsOrSize[b];m_parentsOrSize[b]=a;}}bool connected(int a,int b){return (find(a)==find(b));}int size(int i){return -m_parentsOrSize[find(i)];}private:std::vector<int>m_parentsOrSize;};//ll MOD = INF;//ll MOD = 1000000007;ll MOD = 998244353;bool iskaibun(string s){ll k = s.size();rep(i,0,k/2){if(s[i]!=s[k-1-i]){return false;}}return true;}#include <atcoder/all>using namespace atcoder;string replace(const string&moto,const string &from, const string&too) {int from_len = from.size();string tmp = from + moto;int tmp_len = tmp.size();vector<int> za = z_algorithm(tmp);string ret = "";for (int i = from_len; i < tmp_len;) {if (za[i] >= from_len) {ret += too;i += from_len;} else {ret += tmp[i];i++;}}return ret;}ll zaatu(vector<ll>&A){map<ll,ll>m;for(auto&&x:A)m[x]=0;ll ret = 0;for(auto&&[key,val]:m)val=ret++;for(auto&&x:A)x=m[x];return ret;}//約数列挙vector<ll>enumdiv(ll n){vector<ll>s;for(ll i = 1;i*i<=n;i++){if(n%i==0){s.push_back(i);if(i*i!=n)s.push_back(n/i);}}return s;}vector<ll> topo_sort(vector<vector<ll>>&G,vector<ll>&nyu_cnt,ll v){vector<ll>ret;priority_queue<ll,vector<ll>,greater<ll>>pq;rep(i,0,v){if(nyu_cnt[i]==0)pq.push(i);}while(!pq.empty()){ll pos = pq.top();pq.pop();for(ll i:G[pos]){nyu_cnt[i]--;if(nyu_cnt[i]==0)pq.push(i);}ret.push_back(pos);}return ret;}vector<pair<ll,ll>> soinsu_bunkai(ll x){vector<pair<ll,ll>>ret;rep(i,2,sqrt(x)+1){if(x%i==0){ll cnt{};while(x%i==0){x/=i;cnt++;}ret.push_back({i,cnt});}}if(x!=1)ret.push_back({x,1});return ret;}const int MAX = 1010000;long long fac[MAX], finv[MAX], inv[MAX];void COMinit(){fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (int i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i % MOD;inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;finv[i] = finv[i - 1] * inv[i] % MOD;}}long long COM(int n, int k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}vector<bool> isprime;vector<int> Era(int n) {isprime.resize(n, true);vector<int> res;isprime[0] = false; isprime[1] = false;for (int i = 2; i < n; ++i) isprime[i] = true;for (int i = 2; i < n; ++i) {if (isprime[i]) {res.push_back(i);for (int j = i*2; j < n; j += i) isprime[j] = false;}}return res;}using mint = modint998244353;template<class T>struct DualSegmentTree{virtual void c(T&, const T&) = 0;ll size = 1, rank = 0;vector<T> lazy;const T def_lazy;DualSegmentTree(ll n, const T& def_value, const T& def_lazy): def_lazy(def_lazy){while(size < n){size *= 2;rank++;}lazy.assign(size * 2, def_lazy);for(ll i = size; i < size * 2; i++) lazy[i] = def_value;}DualSegmentTree(const vector<T>& v, const T& def_lazy): def_lazy(def_lazy){while(size < v.size()){size *= 2;rank++;}lazy.assign(size * 2, def_lazy);for(ll i = 0; i < v.size(); i++) lazy[size + i] = v[i];}void push(ll at){if(!at) return;ll r = 31 - __builtin_clz(at);for(ll i = r; i > 0; i--){ll a = at >> i;if(lazy[a] != def_lazy){c(lazy[a * 2], lazy[a]);c(lazy[a * 2 + 1], lazy[a]);lazy[a] = def_lazy;}}}T operator[](ll at){at += size;push(at);return lazy[at];}void set(ll at, const T& val){at += size;push(at);lazy[at] = val;}void query(ll l, ll r, const T& val){if(l >= r) return;l += size;r += size;push(l >> __builtin_ctz(l));push((r >> __builtin_ctz(r)) - 1);for(; l < r; l /= 2, r /= 2){if(l & 1) c(lazy[l++], val);if(r & 1) c(lazy[--r], val);}}};template<class T>struct RAQ : DualSegmentTree<T>{using Base = DualSegmentTree<T>;void c(T& a, const T& b){ a += b; }RAQ(ll n, const T& def_value = T(), const T& def_lazy = T()) : Base(n, def_value, def_lazy){}RAQ(const vector<T>& v, const T& def_lazy = T()) : Base(v, def_lazy){}};void _main(){LL(n);//クエリ2→L,R,l,rを座圧してセグ木に乗せる。あらかじめクエリ先読みして座圧する→うそ//クエリ1→map<string,map<ll,ll>>>で、何時に入室/退出したかを記録しておくvector<ll>tmp;set<ll>tmp_s;auto tuika = [&](ll kore){rep(i,-4,4){if(tmp_s.count(kore+i)==0){tmp_s.insert(kore+i);tmp.pb(kore+i);}}};vector<tuple<ll,string,ll,ll>>queries;rep(i,0,n){STR(x);LL(l,r);tuika(l);tuika(r);queries.pb({3,x,l,r});}LL(q);for(;q--;){LL(t);if(t==1){STR(x);LL(t);tuika(t);queries.pb({1,x,t,-1});}else if(t==2){LL(t);tuika(t);queries.pb({2," ",t,-1});}else{STR(x);LL(l,r);tuika(l);tuika(r);queries.pb({3,x,l,r});}}tmp.pb(-INF);tmp.pb(INF);std::sort(ALL(tmp));RAQ<ll>seg(size(tmp)+10);map<string,map<ll,ll>>buin;for(auto&&[type,x,l,r]:queries){switch (type){case 1:if(buin.count(x)==0){buin[x][0]=0;buin[x][INF]=1;}print((buin[x].upper_bound(l)->second)==0?"Yes":"No");break;case 2:print(seg[lower_bound(ALL(tmp),l)-tmp.begin()]);break;case 3:ll lpos = lower_bound(ALL(tmp),l)-tmp.begin();ll rpos = lower_bound(ALL(tmp),r)-tmp.begin();seg.query(lpos,rpos+1,1);if(buin.count(x)==0){buin[x][0]=0;buin[x][INF]=1;}buin[x][(l)]=1;buin[x][r+1]=0;break;}}}