#902856 (C++14) No.2421 entersys?

提出ソース

結果

問題	No.2421 entersys?
ユーザー	yurina256
提出日時	2023-08-12 15:03:50
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	9,665 bytes
コンパイル時間	4,990 ms
コンパイル使用メモリ	252,740 KB
実行使用メモリ	14,592 KB
最終ジャッジ日時	2024-11-19 23:07:39
合計ジャッジ時間	58,266 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 10,496 KB
testcase_01	WA	-
testcase_02	WA	-
testcase_03	AC	3 ms 10,624 KB
testcase_04	AC	4 ms 10,624 KB
testcase_05	AC	12 ms 12,672 KB
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	TLE	-
testcase_12	TLE	-
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	TLE	-
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	TLE	-
testcase_20	TLE	-
testcase_21	WA	-
testcase_22	TLE	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<bits/stdc++.h>
#include <atcoder/all>
using namespace std; 
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define length size()
//#define int long long
#define ll long long
constexpr ll inf = 1001001001001001001ll;
constexpr ll mod = /* 1000000007*/ 998244353;
constexpr double pi = 3.141592653589793;
//小数出力
//cout << std::setprecision(12);
//imos
void to_ruiseki(vector<int> &vec){
    for(int i=1;i<(int)vec.size();i++){
        vec[i] += vec[i-1];
    }
}
void to_2druiseki(vector<vector<int>> &vec){
    rep(i,vec.size()){
        rep(j,vec[0].size()){
            int s = 0;
            if(i!=0) s += vec[i-1][j];
            if(j!=0) s += vec[i][j-1];
            if(i!=0 && j!=0) s -= vec[i-1][j-1];
            s += vec[i][j];
            vec[i][j] = s;
        }
    }
}
//modpow(a,n,mod)
int modpow(int a, int n, int mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//素因数分解
vector<pair<int,int>> p_fact(int N) {
    vector<pair<int,int>> res;
    for (int a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        int ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({a, ex});
    }

    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}
//ctoi
int ctoi(const char c){
  switch(c){
    case '0': return 0;
    case '1': return 1;
    case '2': return 2;
    case '3': return 3;
    case '4': return 4;
    case '5': return 5;
    case '6': return 6;
    case '7': return 7;
    case '8': return 8;
    case '9': return 9;
    default :  throw runtime_error("hoge");
  }
}
//max
template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
//min
template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
//print
void print() { cout << '\n'; }
template<typename T>
void print(const T &t) { cout << t << '\n'; }
template<typename Head, typename... Tail>
void print(const Head &head, const Tail &... tail) {
    cout << head << ' ';
    print(tail...);
}
//join
template<typename T> string join(vector<T> &vec ,const string &sp){
    int si = vec.length;
    if(si==0){
        return "";
    }else{
        stringstream ss;
        rep(i,si-1){
            ss << vec[i] << sp;
        }
        ss << vec[si - 1];
        return ss.str();
    }
}
//木の直径
int tree_diameter(vector<vector<int>> &vec){
    //0-indexed
    queue<pair<int,int>> que;
    vector<bool> is_searched(vec.size(),false);
    que.push(make_pair(0,0));
    int max_d = 0;
    int max_e = 0;
    while(!que.empty()){
        int e = que.front().first;
        int distance = que.front().second;
        is_searched[e] = true;
        if(max_d<distance){
            max_d = distance;
            max_e = e;
        }
        que.pop();
        rep(i,vec[e].size()){
            if(!is_searched[vec[e][i]]){
                que.push( make_pair( vec[e][i], distance + 1 ) );
            }
        }
    }
    fill(is_searched.begin(),is_searched.end(),false);
    que.push(make_pair(max_e,0));
    max_d = 0;
    max_e = 0;
    
    while(!que.empty()){
        int e = que.front().first;
        int distance = que.front().second;
        is_searched[e] = true;
        if(max_d<distance){
            max_d = distance;
            max_e = e;
        }
        que.pop();
        rep(i,vec[e].size()){
            if(!is_searched[vec[e][i]]){
                que.push( make_pair( vec[e][i], distance + 1 ) );
            }
        }
    }
    return max_d;
}
//uf 根:root(x) 判定:issame(x,y) 結合:unite(x,y) 大きさ:size(x)
int getlongpath(vector<vector<int>> &vec,int st){
    queue<pair<int,int>> que;
    vector<bool> is_searched(vec.size(),false);
    is_searched[st] = true;
    que.push(make_pair(st,0));
    int max_d = 0;
    int max_e = 0;
    while(!que.empty()){
        int e = que.front().first;
        int distance = que.front().second;
        if(max_d<distance){
            max_d = distance;
            max_e = e;
        }
        que.pop();
        rep(i,vec[e].size()){
            if(!is_searched[vec[e][i]]){
                que.push( make_pair( vec[e][i], distance + 1 ) );
                is_searched[vec[e][i]] = true;
            }
        }
    }
    fill(is_searched.begin(),is_searched.end(),false);
    que.push(make_pair(max_e,0));
    return max_d;
}
struct UnionFind {
    vector<int> par, rank, siz;

    // 構造体の初期化
    UnionFind(int n) : par(n,-1), rank(n,0), siz(n,1) { }

    // 根を求める
    int root(int x) {
        if (par[x]==-1) return x; // x が根の場合は x を返す
        else return par[x] = root(par[x]); // 経路圧縮
    }

    // x と y が同じグループに属するか (= 根が一致するか)
    bool issame(int x, int y) {
        return root(x)==root(y);
    }

    // x を含むグループと y を含むグループを併合する
    bool unite(int x, int y) {
        int rx = root(x), ry = root(y); // x 側と y 側の根を取得する
        if (rx==ry) return false; // すでに同じグループのときは何もしない
        // union by rank
        if (rank[rx]<rank[ry]) swap(rx, ry); // ry 側の rank が小さくなるようにする
        par[ry] = rx; // ry を rx の子とする
        if (rank[rx]==rank[ry]) rank[rx]++; // rx 側の rank を調整する
        siz[rx] += siz[ry]; // rx 側の siz を調整する
        return true;
    }

    // x を含む根付き木のサイズを求める
    int size(int x) {
        return siz[root(x)];
    }
};
vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({a, ex});
    }

    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}
class BIT
{
public:

	BIT() = default;

	// 長さ size の数列で初期化
	explicit BIT(size_t size)
		: m_bit(size + 1) {}

	// 数列で初期化
	explicit BIT(const std::vector<long long>& v)
		: BIT(v.size())
	{
		for (int i = 0; i < (int)v.size(); ++i)
		{
			add((i + 1), v[i]);
		}
	}

	// 閉区間 [1, r] の合計を返す (1-based indexing)
	long long sum(int r) const
	{
		long long ret = 0;

		for (; 0 < r; r -= (r & -r))
		{
			ret += m_bit[r];
		}

		return ret;
	}

	// 閉区間 [l, r] の合計を返す (1-based indexing)
	long long sum(int l, int r) const
	{
		return (sum(r) - sum(l - 1));
	}

	// 数列の i 番目の要素を加算 (1-based indexing)
	void add(int i, long long value)
	{
		for (; i < (int)m_bit.size(); i += (i & -i))
		{
			m_bit[i] += value;
		}
	}

private:

	std::vector<long long> m_bit;
};

// Binary Indexed Tree (1.2 区間加算対応)
// 1-based indexing
class BIT_RAQ
{
public:

	BIT_RAQ() = default;

	explicit BIT_RAQ(size_t size)
		: m_bit0(size)
		, m_bit1(size) {}

	explicit BIT_RAQ(const std::vector<long long>& v)
		: m_bit0(v)
		, m_bit1(v.size()) {}

	// 閉区間 [1, r] の合計を返す (1-based indexing)
	long long sum(int r) const
	{
		return (m_bit0.sum(r) + m_bit1.sum(r) * r);
	}

	// 閉区間 [l, r] の合計を返す (1-based indexing)
	long long sum(int l, int r) const
	{
		return (sum(r) - sum(l - 1));
	}

	// 数列の i 番目の要素を加算 (1-based indexing)
	void add(int i, long long value)
	{
		m_bit0.add(i, value);
	}

	// 閉区間 [l, r] の要素を加算 (1-based indexing)
	void add(int l, int r, long long value)
	{
		m_bit0.add(l, (-value * (l - 1)));
		m_bit0.add((r + 1), (value * r));
		m_bit1.add(l, value);
		m_bit1.add((r + 1), -value);
	}

private:

	BIT m_bit0;

	BIT m_bit1;
};
int bs(vector<pair<int,int>> &vec,int n){
    int left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    int right = (int)vec.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

    /* どんな二分探索でもここの書き方を変えずにできる！ */
    while (right - left > 1) {
        int mid = left + (right - left) / 2;

        if (n <= vec[mid].second) right = mid;
        else left = mid;
    }

    /* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
    return (int)(right < (int)vec.size() && vec[right].first <= n);
}
signed main(void){
  int n;
  cin >> n;
  map<string,vector<pair<int,int>>> mp;
  rep(i,n){
  	string x;
    int l,r;
    cin >> x >> l >> r;
    if(mp.count(x)){
    	mp[x].push_back({l,r});
    }else{
    	mp[x] = vector<pair<int,int>>(0);
      	mp[x].push_back({l,r});
    }
  }
  	for(pair<string,vector<pair<int,int>>> p:mp){
		sort(p.second.begin(),p.second.end());
	}
  int q;
  cin >> q;
  rep(k,q){
  	int qt;
    cin >> qt;
    if(qt == 1){
    	string x;
      int t;
      cin >> x >> t;
      print((bs(mp[x],t))?"Yes":"No");
    }else if(qt == 2){
    	int t;
      	cin >> t;
      int s = 0;
  	for(pair<string,vector<pair<int,int>>> p:mp){
		s += bs(p.second,t);
	}
      print(s);
    }else if(qt==3){
    	string x;
      int l,r;
      cin >> x >> l >> r;
      mp[x].push_back({l,r});
      sort(mp[x].begin(),mp[x].end());
    }
  }
}

yukicoder

結果

テストケース

ソースコード