提出 #70624008

---

ソースコード 拡げる

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#ifdef jlocal
#include<jdebug/debug.hpp>
#else
#define debug(...) 0;
#endif

using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef vector<pii> vii;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#if defined(__LP64__) || defined(_WIN64)
typedef __int128 lll;
#else
typedef long long lll;
#endif

#define pcount(x) __builtin_popcount(x)
#define pcountll(x) __builtin_popcountll(x)
#define all(x) x.begin(),x.end()

const ld pi = 3.14159265358979323846L;
const ld sqrt2 = 1.41421356237309504880L;

template<class T>
istream& operator>>(istream& in, vector<T> &a){
	for (int i = 0; i < a.size(); i ++)
		in >> a[i];
	return in;
}

template<class T>
ostream& operator<<(ostream& out, vector<T> &a){
	for (int i = 0; i < a.size(); i ++){
		if (i > 0) out << ' ';
		out << a[i];
	}
	return out;
}

#if defined(__LP64__) || defined(_WIN64)

istream& operator>>(istream& in, __int128 &x){
	string S;
	in >> S;
	for (char &y : S){
		x *= 10;
		x += (y - '0');
	}
	return in;
}

ostream& operator<<(ostream& out, __int128 &x){
	string s;
	while(x > 0){
		s.push_back((x % 10) + '0');
		x /= 10;
	}
	if (s.size() == 0)
		s.push_back('0');
	reverse(all(s));
	return out << s;
}

#endif

mt19937_64 MT64;
void pre_init() {
	MT64 = mt19937_64(chrono::system_clock::now().
	time_since_epoch().count());
}

template<
  class T1, // answer value stored on nodes
  class T2, // lazy update value stored on nodes
  T1 merge(T1, T1), 
  void pushUpd(T2& /*padre*/, T2& /*hijo*/, int, int, int, int), // push update value from a node to another. parent -> child
  void applyUpd(T2&, T1&, int, int)           // apply the update value of a node to its answer value. upd -> ans
>
struct SegmentTreeLazy{
  vector<T1> ST;
  vector<T2> lazy;
  vector<bool> upd;
  int n;
  void build(int i, int l, int r, vector<T1>&values){
    if (l == r){
      ST[i] = values[l];
      return;
    }
    build(i << 1, l, (l + r) >> 1, values);
    build(i << 1 | 1, (l + r) / 2 + 1, r, values);
    ST[i] = merge(ST[i << 1], ST[i << 1 | 1]);
  }
  SegmentTreeLazy(vector<T1>&values){
    n = values.size();
    ST.resize(n << 2 | 3);
    lazy.resize(n << 2 | 3);
    upd.resize(n << 2 | 3, false);
    build(1, 0, n - 1, values);
  }
  SegmentTreeLazy(int n, T1 x) : n(n){
    vector<T1> v(n, x);
    ST.resize(n << 2 | 3);
    upd.resize(n << 2 | 3, false);
    lazy.resize(n << 2 | 3);
    build(1, 0, n - 1, v);
  }
  SegmentTreeLazy(){}
  void push(int i, int l, int r){
    if (upd[i]){
      applyUpd(lazy[i], ST[i], l, r);
      if (l != r){
        pushUpd(lazy[i], lazy[i << 1], l, r, l, (l + r) / 2);
        pushUpd(lazy[i], lazy[i << 1 | 1], l, r, (l + r) / 2 + 1, r);
        upd[i << 1] = 1;
        upd[i << 1 | 1] = 1;
      }
      lazy[i] = T2();
      upd[i] = false;
    }
  }
  void update(int i, int l, int r, int a, int b, T2 &u){
    if (l >= a and r <= b){
      pushUpd(u, lazy[i], a, b, l, r);
      upd[i] = true;
    }
    push(i, l, r);
    if (l > b or r < a) return;
    if (l >= a and r <= b) return;
    update(i << 1, l, (l + r) >> 1, a, b, u);
    update(i << 1 | 1, (l + r) / 2 + 1, r, a, b, u);
    ST[i] = merge(ST[i << 1], ST[i << 1 | 1]);
  }
  void update(int a, int b, T2 u){
    if (a > b){
      update(0, b, u);
      update(a, n - 1, u);
      return ;
    }
    update(1, 0, n - 1, a, b, u);
  }
  T1 query(int i, int l, int r, int a, int b){
    push(i, l, r);
    if (a <= l and r <= b)
      return ST[i];
    int mid = (l + r) >> 1;
    if (mid < a)
      return query(i << 1 | 1, mid + 1, r, a, b);
    if (mid >= b) 
      return query(i << 1, l, mid, a, b);
    return merge(query(i << 1, l, mid, a, b), query(i << 1 | 1, mid + 1, r, a, b));
  }
  T1 query(int a, int b){
    if (a > b){
      return merge(query(a, n - 1), query(0, b));
    }
    return query(1, 0, n - 1, a, b);
  }
  void get_leaves(int i, int l, int r, vector<T1> &res){
    push(i, l, r);
    if (l == r){
      res[l] = ST[i];
      return;
    }
    get_leaves(i << 1, l, (l + r) / 2, res);
    get_leaves(i << 1 | 1, (l + r) / 2 + 1, r, res);
  }
  void get_leaves(vector<T1> &res) {
    res.resize(n);
    get_leaves(1, 0, n - 1, res);
  }
};

template<class T>
T merge(T a, T b){
	if (a.first == b.first){
		return {a.first, a.second + b.second};
	}
  	return max(a, b);
}

template<class U>
void pushUpd(U &u1, U &u2, int l1, int r1, int l2, int r2){
  u2 += u1;
}

template<class T, class U>
void applyUpd(U &u, T &v, int l, int r){
  v.first += u;
}



void solve(int caso){
	int n, q;
	cin >> n >> q;
	vector<set<tuple<int, int, int>>> intervalos(60);
	for (int i = 0; i < 60; i ++){
		intervalos[i].insert({0, n - 1, 0});
	}
	SegmentTreeLazy<pii, int, merge<pii>, pushUpd<int>, applyUpd<pii, int>> stl(n, {0, 1});

	for (int i = 0; i < q; i ++){
		int t, l, r;
		cin >> t >> l >> r;
		l --; r --;
		debug(t, l, r);
		if (t == 3){
			auto [a1, a2] = stl.query(l, r);
			cout << a1 << " " << a2 << '\n';
		}
		else if (t == 1){
			int x;
			cin >> x;
			x --;
			auto it = intervalos[x].lower_bound({l, -1, -1});
			if (it == intervalos[x].end() or get<0>(*it) > l)
				it --;
			vector<set<tuple<int, int, int>>::iterator> todel;
			vector<tuple<int, int, int> > toadd;
			int L = l, R = r;
			debug(intervalos[x]);
			debug(*it);
			while(it != intervalos[x].end() and max(get<0>(*it), l) <= min(get<1>(*it), r)){
				auto [left, right, b] = *it;
				debug(left, right, b);
				todel.push_back(it);
				if (left < l and b == 0){
					toadd.emplace_back(left, l - 1, b);
				}
				if (right > r and b == 0){
					toadd.emplace_back(r + 1, right, b);
				}
				if (b == 0){
					stl.update(max(L, left), min(R, right), 1);
				}

				if (left < l and b == 1){
					L = left;
				}
				if (right > r and b == 1){
					R = right;
				}
				it ++;
			}
			toadd.emplace_back(L, R, 1);
			for (auto it : todel){
				intervalos[x].erase(it);
			}
			for (auto X : toadd){
				intervalos[x].insert(X);
			}
			debug(intervalos[x]);
		}
		else{
			int x;
			cin >> x;
			x --;
			auto it = intervalos[x].lower_bound({l, -1, -1});
			if (it == intervalos[x].end() or get<0>(*it) > l)
				it --;
			vector<set<tuple<int, int, int>>::iterator> todel;
			vector<tuple<int, int, int> > toadd;
			int L = l, R = r;
			while(it != intervalos[x].end() and max(get<0>(*it), l) <= min(get<1>(*it), r)){
				auto [left, right, b] = *it;
				todel.push_back(it);
				if (left < l and b == 1){
					toadd.emplace_back(left, l - 1, b);
				}
				if (right > r and b == 1){
					toadd.emplace_back(r + 1, right, b);
				}
				if (b == 1){
					stl.update(max(L, left), min(R, right), -1);
				}

				if (left < l and b == 0){
					L = left;
				}
				if (right > r and b == 0){
					R = right;
				}
				it ++;
			}
			toadd.emplace_back(L, R, 0);
			for (auto it : todel){
				intervalos[x].erase(it);
			}
			for (auto X : toadd){
				intervalos[x].insert(X);
			}
		}
	}
}

int main(){
#ifndef jlocal
	ios::sync_with_stdio(0); cin.tie(0);
#endif
	pre_init();

	int t = 1;
	for (int i = 1; i <= t; i ++){
		solve(i);
	}
	return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function 'void solve(int)':
./Main.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 0;
      |                    ^
./Main.cpp:216:17: note: in expansion of macro 'debug'
  216 |                 debug(t, l, r);
      |                 ^~~~~
./Main.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 0;
      |                    ^
./Main.cpp:231:25: note: in expansion of macro 'debug'
  231 |                         debug(intervalos[x]);
      |                         ^~~~~
./Main.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 0;
      |                    ^
./Main.cpp:232:25: note: in expansion of macro 'debug'
  232 |                         debug(*it);
      |                         ^~~~~
./Main.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 0;
      |                    ^
./Main.cpp:235:33: note: in expansion of macro 'debug'
  235 |                                 debug(left, right, b);
      |                                 ^~~~~
./Main.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 0;
      |                    ^
./Main.cpp:262:25: note: in expansion of macro 'debug'
  262 |                         debug(intervalos[x]);
      |                         ^~~~~
./Main.cpp:203:16: warning: unused parameter 'caso' [-Wunused-parameter]
  203 | void solve(int caso){
      |            ~~~~^~~~
./Main.cpp: In instantiation of 'void pushUpd(U&, U&, int, int, int, int) [with U = int]':
./Main.cpp:210:71:   required from here
  210 |         SegmentTreeLazy<pii, int, merge<pii>, pushUpd<int>, applyUpd<pii, int>> stl(n, {0, 1});
      |                                                                              ^~
./Main.cpp:192:32: warning: unused parameter 'l1' [-Wunused-parameter]
  192 | void pushUpd(U &u1, U &u2, int l1, int r1, int l2, int r2){
      |                            ~~~~^~
./Main.cpp:192:40: warning: unused parameter 'r1' [-Wunused-parameter]
  192 | void pushUpd(U &u1, U &u2, int l1, int r1, int l2, int r2){
      |                                    ~~~~^~
./Main.cpp:192:48: warning: unused parameter 'l2' [-Wunused-parameter]
  192 | void pushUpd(U &u1, U &u2, int l1, int r1, int l2, int r2){
      |                                            ~~~~^~
./Main.cpp:192:56: warning: unused parameter 'r2' [-Wunused-parameter]
  192 | void pushUpd(U &u1, U &u2, int l1, int r1, int l2, int r2){
      |                                                    ~~~~^~
./Main.cpp: In instantiation of 'void applyUpd(U&, T&, int, int) [with T = std::pair<int, int>; U = int]':
./Main.cpp:210:71:   required from here
  210 |         SegmentTreeLazy<pii, int, merge<pii>, pushUpd<int>, applyUpd<pii, int>> stl(n, {0, 1});
      |                                                                              ^~
./Main.cpp:197:31: warning: unused parameter 'l' [-Wunused-parameter]
  197 | void applyUpd(U &u, T &v, int l, int r){
      |                           ~~~~^
./Main.cpp:197:38: warning: unused parameter 'r' [-Wunused-parameter]
  197 | void applyUpd(U &u, T &v, int l, int r){
      |                                  ~~~~^

ジャッジ結果