結果

問題 No.2421 entersys?
ユーザー bluebery1001bluebery1001
提出日時 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 -
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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>inline
    bool 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-find
class 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;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0