oj.uz

답안 #328715

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
328715 2020-11-17T18:13:12 Z jc713 가로등 (APIO19_street_lamps) C++17
100 / 100
 4489 ms 124508 KB 
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>

using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>,
    rb_tree_tag, tree_order_statistics_node_update>;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using db = double; 
using str = string; // yay python!

using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>; 
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>; 
using vpd = vector<pd>;

#define tcT template<class T
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 

// pairs
#define mp make_pair
#define f first
#define s second

// vectors
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const int IINF = 1e9;
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

// helper funcs
constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down

tcT> bool ckmin(T& a, const T& b) {
    return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0; }

#define tcTU tcT, class U
tcTU> T fstTrue(T lo, T hi, U f) {
    hi ++; assert(lo <= hi); // assuming f is increasing
    while (lo < hi) { // find first index such that f is true 
        T mid = lo+(hi-lo)/2;
        f(mid) ? hi = mid : lo = mid+1; 
    } 
    return lo;
}
tcTU> T lstTrue(T lo, T hi, U f) {
    lo --; assert(lo <= hi); // assuming f is decreasing
    while (lo < hi) { // find first index such that f is true 
        T mid = lo+(hi-lo+1)/2;
        f(mid) ? lo = mid : hi = mid-1;
    } 
    return lo;
}
tcT> void remDup(vector<T>& v) { // sort and remove duplicates
    sort(all(v)); v.erase(unique(all(v)),end(v)); }
tcTU> void erase(T& t, const U& u) { // don't erase
    auto it = t.find(u); assert(it != end(t));
    t.erase(u); } // element that doesn't exist from (multi)set

// INPUT
#define tcTUU tcT, class ...U
tcT> void re(complex<T>& c);
tcTU> void re(pair<T,U>& p);
tcT> void re(vector<T>& v);
tcT, size_t SZ> void re(AR<T,SZ>& a);

tcT> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
tcTUU> void re(T& t, U&... u) { re(t); re(u...); }

tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; }
tcTU> void re(pair<T,U>& p) { re(p.f,p.s); }
tcT> void re(vector<T>& x) { trav(a,x) re(a); }
tcT, size_t SZ> void re(AR<T,SZ>& x) { trav(a,x) re(a); }

// TO_STRING
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
str ts(bool b) { 
    #ifdef LOCAL
        return b ? "true" : "false"; 
    #else 
        return ts((int)b);
    #endif
}
tcT> str ts(complex<T> c) { 
    stringstream ss; ss << c; return ss.str(); }
str ts(vector<bool> v) {
    str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
    res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) {
    str res = ""; F0R(i,SZ) res += char('0'+b[i]);
    return res; }
tcTU> str ts(pair<T,U> p);
tcT> str ts(T v) { // containers with begin(), end()
    #ifdef LOCAL
        bool fst = 1; str res = "{";
        for (const auto& x: v) {
            if (!fst) res += ", ";
            fst = 0; res += ts(x);
        }
        res += "}"; return res;
    #else
        bool fst = 1; str res = "";
        for (const auto& x: v) {
            if (!fst) res += " ";
            fst = 0; res += ts(x);
        }
        return res;

    #endif
}
tcTU> str ts(pair<T,U> p) {
    #ifdef LOCAL
        return "("+ts(p.f)+", "+ts(p.s)+")"; 
    #else
        return ts(p.f)+" "+ts(p.s);
    #endif
}

// OUTPUT
tcT> void pr(T x) { cout << ts(x); }
tcTUU> void pr(const T& t, const U&... u) { 
    pr(t); pr(u...); }
void ps() { pr("\n"); } // print w/ spaces
tcTUU> void ps(const T& t, const U&... u) { 
    pr(t); if (sizeof...(u)) pr(" "); ps(u...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
tcTUU> void DBG(const T& t, const U&... u) {
    cerr << ts(t); if (sizeof...(u)) cerr << ", ";
    DBG(u...); }
#ifdef LOCAL // compile with -DLOCAL, chk -> fake assert
    #define dbg(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
    #define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \
         << __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);
#else
    #define dbg(...) 0
    #define chk(...) 0
#endif

// FILE I/O
void setIn(str s) { freopen(s.c_str(),"r",stdin); }
void setOut(str s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
void setIO(str s = "") {
    unsyncIO();
    // cin.exceptions(cin.failbit); 
    // throws exception when do smth illegal
    // ex. try to read letter into int
    if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

template<class T> struct Seg { // comb(ID,b) = b
	const T ID = 0; T comb(T a, T b) { return a+b; }
	int n; vector<T> seg;
	void init(int _n) { n = _n; seg.assign(2*n,ID); }
	void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
	void upd(int p, T val) { // set val at position p
		seg[p += n] += val; for (p /= 2; p; p /= 2) pull(p); }
	void clean(int p, T val) { // set val at position p
		seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
	T query(int l, int r) {	// sum on interval [l, r]
		T ra = ID, rb = ID;
		for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if (l&1) ra = comb(ra,seg[l++]);
			if (r&1) rb = comb(seg[--r],rb);
		}
		return comb(ra,rb);
	}
};

struct i{
	int t, l, r, type, qidx;
	i(int _t, int _l, int _r, int _type = -1):t(_t),l(_l),r(_r),type(_type){} // 0 = add, 1 = remove, 2 = query
};

const ll MAX = 300010;

ll ans[MAX];

bitset<MAX> state;

struct cmp {
    bool operator()(const i& x, const i& y) const { return x.l < y.l; }
};

Seg<ll> tree1, tree2;
Seg<int> n1, n2;

void cdq(vector<i>& d, int l, int r){
	if(l + 1 == r){
		sort(all(d), [](const i& a, const i& b){return a.l < b.l;});
		return;
	}
	int m = (l + r) / 2;
	vector<i> left, right;
	trav(a, d)
		if(a.t < m)
			left.pb(a);
		else
			right.pb(a);
	cdq(left, l, m);
	cdq(right, m, r);
	int i = 0;
	int k = 0;
	set<int> r1, r2;
	F0R(j, sz(right)){
		while(i < sz(left) && left[i].l <= right[j].l){
			d[k++] = left[i];
			if(left[i].type == 0){
				n1.upd(left[i].r, 1);
				tree1.upd(left[i].r, MAX - left[i].t);
				r1.insert(left[i].r);
			}
			else if(left[i].type == 1){
				n2.upd(left[i].r, 1);
				tree2.upd(left[i].r, MAX - left[i].t);
				r2.insert(left[i].r);
			}
			i++;
		}
		if(right[j].type == 2){
			ans[right[j].qidx] += (tree1.query(right[j].r - 1, MAX - 1) - n1.query(right[j].r - 1, MAX - 1) * (MAX - right[j].t));
			ans[right[j].qidx] -= (tree2.query(right[j].r - 1, MAX - 1) - n2.query(right[j].r - 1, MAX - 1) * (MAX - right[j].t));
		}
		d[k++] = right[j];
	}
	while(i < sz(left))
		d[k++] = left[i++];
	trav(a, r1)
		tree1.clean(a, 0), n1.clean(a, 0);
	trav(a, r2)
		tree2.clean(a, 0), n2.clean(a, 0);
}

int main(){
    setIO();
	tree1.init(524288), tree2.init(524288);
	n1.init(524288), n2.init(524288);
	vector<i> d;
	int n, q;
	cin >> n >> q;
	set<i, cmp> segs;
	string s;
	cin >> s;
	F0R(a, n){
		state[a] = (s[a] == '1');
		if(state[a] == 0)
			continue;
		if(a != 0 && state[a - 1] == 1){
			auto t = --segs.end();
			i temp(t->t, t->l, t->r + 1);
			segs.erase(t);
			segs.insert(temp);
		}
		else
			segs.insert(i(0, a, a));
	}
	set<int> stor;
	FOR(a, 1, q + 1){
		string s;
		cin >> s;
		if(s == "toggle"){
			int x;
			cin >> x;
			x--;
			state[x] = state[x] ^ 1;
			if(state[x] == 1){
				i nxt(a, x, x);
				auto t1 = segs.ub({IINF, x, IINF});
				if(t1 != segs.begin() && (--t1)->r == x - 1)
					nxt.l = t1->l, d.pb({t1->t, t1->l, t1->r, 0}), d.pb({a, t1->l, t1->r, 1}), segs.erase(t1);
				auto t2 = segs.ub({IINF, x, IINF});
				if(t2 != segs.end() && t2->l == x + 1)
					nxt.r = t2->r, d.pb({t2->t, t2->l, t2->r, 0}), d.pb({a, t2->l, t2->r, 1}), segs.erase(t2);
				segs.insert(nxt);
			}
			else{
				auto t = segs.ub({IINF, x, IINF});
				t--;
				i temp = *t;
				segs.erase(t);
				d.pb({temp.t, temp.l, temp.r, 0});
				d.pb({a, temp.l, temp.r, 1});
				if(temp.l != x)
					segs.insert({a, temp.l, x - 1});
				if(temp.r != x)
					segs.insert({a, x + 1, temp.r});
			}
		}
		else{
			int A, B;
			cin >> A >> B;
			A--, B--;
			d.pb({a, A, B, 2});
			d.back().qidx = a;
			stor.insert(a);
		}
	}
	trav(a, segs)
		d.pb({q + 1, a.l, a.r, 1}), d.pb({a.t, a.l, a.r, 0});
	sort(all(d), [](const i& a, const i& b){return (a.t == b.t ? a.type < b.type : a.t < b.t);});
	cdq(d, 0, q + 2);
	trav(a, stor)
		cout << ans[a] << endl;
    // you should actually read the stuff at the bottom
}
 
/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/

Compilation message

street_lamps.cpp: In function 'void setIn(str)':
street_lamps.cpp:190:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  190 | void setIn(str s) { freopen(s.c_str(),"r",stdin); }
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void setOut(str)':
street_lamps.cpp:191:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  191 | void setOut(str s) { freopen(s.c_str(),"w",stdout); }
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 24940 KB Output is correct
2 Correct 15 ms 24940 KB Output is correct
3 Correct 15 ms 25068 KB Output is correct
4 Correct 15 ms 25068 KB Output is correct
5 Correct 15 ms 25068 KB Output is correct
6 Correct 16 ms 24940 KB Output is correct
7 Correct 16 ms 24940 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1606 ms 66032 KB Output is correct
2 Correct 1669 ms 66532 KB Output is correct
3 Correct 2017 ms 67652 KB Output is correct
4 Correct 3483 ms 119536 KB Output is correct
5 Correct 3749 ms 104040 KB Output is correct
6 Correct 3512 ms 124508 KB Output is correct
7 Correct 2398 ms 68232 KB Output is correct
8 Correct 2489 ms 69852 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 25196 KB Output is correct
2 Correct 20 ms 25196 KB Output is correct
3 Correct 20 ms 25196 KB Output is correct
4 Correct 20 ms 25068 KB Output is correct
5 Correct 3270 ms 79204 KB Output is correct
6 Correct 4489 ms 99112 KB Output is correct
7 Correct 3795 ms 104064 KB Output is correct
8 Correct 2711 ms 70128 KB Output is correct
9 Correct 1200 ms 56624 KB Output is correct
10 Correct 1328 ms 63076 KB Output is correct
11 Correct 1338 ms 64612 KB Output is correct
12 Correct 2647 ms 68444 KB Output is correct
13 Correct 2723 ms 69876 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 25196 KB Output is correct
2 Correct 20 ms 25324 KB Output is correct
3 Correct 21 ms 25324 KB Output is correct
4 Correct 20 ms 25316 KB Output is correct
5 Correct 3359 ms 111776 KB Output is correct
6 Correct 3570 ms 115748 KB Output is correct
7 Correct 3633 ms 114792 KB Output is correct
8 Correct 3706 ms 119708 KB Output is correct
9 Correct 1671 ms 70064 KB Output is correct
10 Correct 1523 ms 71980 KB Output is correct
11 Correct 1679 ms 71424 KB Output is correct
12 Correct 1499 ms 72000 KB Output is correct
13 Correct 1687 ms 71524 KB Output is correct
14 Correct 1506 ms 69808 KB Output is correct
15 Correct 2657 ms 68508 KB Output is correct
16 Correct 2689 ms 69636 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 24940 KB Output is correct
2 Correct 15 ms 24940 KB Output is correct
3 Correct 15 ms 25068 KB Output is correct
4 Correct 15 ms 25068 KB Output is correct
5 Correct 15 ms 25068 KB Output is correct
6 Correct 16 ms 24940 KB Output is correct
7 Correct 16 ms 24940 KB Output is correct
8 Correct 1606 ms 66032 KB Output is correct
9 Correct 1669 ms 66532 KB Output is correct
10 Correct 2017 ms 67652 KB Output is correct
11 Correct 3483 ms 119536 KB Output is correct
12 Correct 3749 ms 104040 KB Output is correct
13 Correct 3512 ms 124508 KB Output is correct
14 Correct 2398 ms 68232 KB Output is correct
15 Correct 2489 ms 69852 KB Output is correct
16 Correct 19 ms 25196 KB Output is correct
17 Correct 20 ms 25196 KB Output is correct
18 Correct 20 ms 25196 KB Output is correct
19 Correct 20 ms 25068 KB Output is correct
20 Correct 3270 ms 79204 KB Output is correct
21 Correct 4489 ms 99112 KB Output is correct
22 Correct 3795 ms 104064 KB Output is correct
23 Correct 2711 ms 70128 KB Output is correct
24 Correct 1200 ms 56624 KB Output is correct
25 Correct 1328 ms 63076 KB Output is correct
26 Correct 1338 ms 64612 KB Output is correct
27 Correct 2647 ms 68444 KB Output is correct
28 Correct 2723 ms 69876 KB Output is correct
29 Correct 20 ms 25196 KB Output is correct
30 Correct 20 ms 25324 KB Output is correct
31 Correct 21 ms 25324 KB Output is correct
32 Correct 20 ms 25316 KB Output is correct
33 Correct 3359 ms 111776 KB Output is correct
34 Correct 3570 ms 115748 KB Output is correct
35 Correct 3633 ms 114792 KB Output is correct
36 Correct 3706 ms 119708 KB Output is correct
37 Correct 1671 ms 70064 KB Output is correct
38 Correct 1523 ms 71980 KB Output is correct
39 Correct 1679 ms 71424 KB Output is correct
40 Correct 1499 ms 72000 KB Output is correct
41 Correct 1687 ms 71524 KB Output is correct
42 Correct 1506 ms 69808 KB Output is correct
43 Correct 2657 ms 68508 KB Output is correct
44 Correct 2689 ms 69636 KB Output is correct
45 Correct 989 ms 54316 KB Output is correct
46 Correct 1067 ms 54724 KB Output is correct
47 Correct 1921 ms 68620 KB Output is correct
48 Correct 3652 ms 118080 KB Output is correct
49 Correct 1526 ms 66920 KB Output is correct
50 Correct 1533 ms 66688 KB Output is correct
51 Correct 1539 ms 65560 KB Output is correct
52 Correct 1683 ms 67092 KB Output is correct
53 Correct 1668 ms 66216 KB Output is correct
54 Correct 1672 ms 66080 KB Output is correct