oj.uz

Submission #199686

# Submission time Handle Problem Language Result Execution time Memory
199686 2020-02-02T18:45:11 Z rqi Lucky Numbers (RMI19_lucky) C++14
100 / 100
 79 ms 8824 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef double db;
typedef long long ll;
typedef long double ld;
typedef string str;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef complex<ld> cd;
 
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#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)
 
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
 
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define rsz resize
#define ins insert
 
const int MOD = 1e9+7; // 998244353 = (119<<23)+1
const ll INF = 1e18;
const int MX = 2e5+5;
const ld PI = 4*atan((ld)1);
 
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>
 
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define ook order_of_key
#define fbo find_by_order
 
namespace input {
    template<class T> void re(complex<T>& x);
    template<class T1, class T2> void re(pair<T1,T2>& p);
    template<class T> void re(vector<T>& a);
    template<class T, size_t SZ> void re(array<T,SZ>& a);
 
    template<class T> void re(T& x) { cin >> x; }
    void re(double& x) { string t; re(t); x = stod(t); }
    void re(ld& x) { string t; re(t); x = stold(t); }
    template<class T, class... Ts> void re(T& t, Ts&... ts) { 
        re(t); re(ts...); 
    }
 
    template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); }
    template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); }
    template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); }
    template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); }
}
 
using namespace input;
 
namespace output {
    void pr(int x) { cout << x; }
    void pr(long x) { cout << x; }
    void pr(ll x) { cout << x; }
    void pr(unsigned x) { cout << x; }
    void pr(unsigned long x) { cout << x; }
    void pr(unsigned long long x) { cout << x; }
    void pr(float x) { cout << x; }
    void pr(double x) { cout << x; }
    void pr(ld x) { cout << x; }
    void pr(char x) { cout << x; }
    void pr(const char* x) { cout << x; }
    void pr(const string& x) { cout << x; }
    void pr(bool x) { pr(x ? "true" : "false"); }
    template<class T> void pr(const complex<T>& x) { cout << x; }
    
    template<class T1, class T2> void pr(const pair<T1,T2>& x);
    template<class T> void pr(const T& x);
    
    template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
        pr(t); pr(ts...); 
    }
    template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
        pr("{",x.f,", ",x.s,"}"); 
    }
    template<class T> void pr(const T& x) { 
        pr("{"); // const iterator needed for vector<bool>
        bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
        pr("}");
    }
    
    void ps() { pr("\n"); } // print w/ spaces
    template<class T, class... Ts> void ps(const T& t, const Ts&... ts) { 
        pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); 
    }
    
    void pc() { pr("]\n"); } // debug w/ commas
    template<class T, class... Ts> void pc(const T& t, const Ts&... ts) { 
        pr(t); if (sizeof...(ts)) pr(", "); pc(ts...); 
    }
    #define dbg(x...) pr("[",#x,"] = ["), pc(x);
}
 
using namespace output;
 
namespace io {
    void setIn(string s) { freopen(s.c_str(),"r",stdin); }
    void setOut(string s) { freopen(s.c_str(),"w",stdout); }
    void setIO(string s = "") {
        cin.sync_with_stdio(0); cin.tie(0); // fast I/O
        cin.exceptions(cin.failbit); // ex. throws exception when you try to read letter into int
        if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
    }
}
 
using namespace io;
 
template<class T> T invGeneral(T a, T b) {
	a %= b; if (a == 0) return b == 1 ? 0 : -1;
	T x = invGeneral(b,a); 
	return x == -1 ? -1 : ((1-(ll)b*x)/a+b)%b;
}
 
template<class T> struct modular {
	T val; 
	explicit operator T() const { return val; }
	modular() { val = 0; }
	modular(const ll& v) { 
		val = (-MOD <= v && v <= MOD) ? v : v % MOD;
		if (val < 0) val += MOD;
	}
	
	// friend ostream& operator<<(ostream& os, const modular& a) { return os << a.val; }
	friend void pr(const modular& a) { pr(a.val); }
	friend void re(modular& a) { ll x; re(x); a = modular(x); }
   
	friend bool operator==(const modular& a, const modular& b) { return a.val == b.val; }
	friend bool operator!=(const modular& a, const modular& b) { return !(a == b); }
	friend bool operator<(const modular& a, const modular& b) { return a.val < b.val; }
 
	modular operator-() const { return modular(-val); }
	modular& operator+=(const modular& m) { if ((val += m.val) >= MOD) val -= MOD; return *this; }
	modular& operator-=(const modular& m) { if ((val -= m.val) < 0) val += MOD; return *this; }
	modular& operator*=(const modular& m) { val = (ll)val*m.val%MOD; return *this; }
	friend modular pow(modular a, ll p) {
		modular ans = 1; for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans;
	}
	friend modular inv(const modular& a) { 
		auto i = invGeneral(a.val,MOD); assert(i != -1);
		return i;
	} // equivalent to return exp(b,MOD-2) if MOD is prime
	modular& operator/=(const modular& m) { return (*this) *= inv(m); }
	
	friend modular operator+(modular a, const modular& b) { return a += b; }
	friend modular operator-(modular a, const modular& b) { return a -= b; }
	friend modular operator*(modular a, const modular& b) { return a *= b; }
	
	friend modular operator/(modular a, const modular& b) { return a /= b; }
};
 
typedef modular<int> mi;
typedef pair<mi,mi> pmi;
typedef vector<mi> vmi;
typedef vector<pmi> vpmi;

mi tpows[100005][4]; //non3non1, non3 1, 3non1, 31

/**
 * Description: 1D point update, range query. \texttt{comb} 
 	* can be any associative operation. $N$ doesn't have to be a power of 2
 	* (but then \texttt{seg[1]} might not equal \texttt{query(0,N-1)}).
 * Time: O(\log N)
 * Source: 
	* http://codeforces.com/blog/entry/18051
	* KACTL
 * Verification: SPOJ Fenwick
 */

typedef pair<array<mi, 4>, array<int, 4>> T;
//non3non1, non3 1, 3non1, 31
//contain 13? end with 1? Start with 3? size
struct Seg { 
	const T ID = {{0, 0, 0, 0}, {-1, -1, -1, -1}}; // comb(ID,b) must equal b
	T comb(T a, T b) { 
		if(a.s[0] == -1){
			return b;
		}
		if(b.s[0] == -1) return a;
		
		T c = ID;
		
		c.s[3] = a.s[3]+b.s[3];
		
		if(a.s[0] == 1 || b.s[0] == 1 || (a.s[1] == 1 && b.s[2] == 1)){
			c.s[0] = 1;
		}
		else c.s[0] = 0;
		
		if(b.s[1] == 1){
			c.s[1] = 1;
		}
		else c.s[1] = 0;
		
		if(a.s[2] == 1){
			c.s[2] = 1;
		}
		else c.s[2] = 0;
		
		//now update the first parts
		if(a.s[0] == 0){
			if(a.s[1] == 0 && a.s[2] == 0){
				//22
				//take care of equality cases
				c.f[0]+=b.f[0]+b.f[2];
				c.f[1]+=b.f[1]+b.f[3];
				a.f[0]-=1;
			}
			else if(a.s[1] == 1 && a.s[2] == 0){
				//21
				c.f[0]+=b.f[0];
				c.f[1]+=b.f[1];
				a.f[1]-=1;
			}
			else if(a.s[1] == 0 && a.s[2] == 1){
				//32
				c.f[2]+=b.f[0]+b.f[2];
				c.f[3]+=b.f[1]+b.f[3];
				a.f[2]-=1;
			}
			else if(a.s[1] == 1 && a.s[2] == 1){
				//31
				c.f[2]+=b.f[0];
				c.f[3]+=b.f[1];
				a.f[3]-=1;
			}
		}
		int bsz = b.s[3];
		c.f[0]+=a.f[0]*(tpows[bsz][0]+tpows[bsz][2])+a.f[1]*(tpows[bsz][0]);
		c.f[1]+=a.f[0]*(tpows[bsz][1]+tpows[bsz][3])+a.f[1]*(tpows[bsz][1]);
		c.f[2]+=a.f[2]*(tpows[bsz][0]+tpows[bsz][2])+a.f[3]*(tpows[bsz][0]);
		c.f[3]+=a.f[2]*(tpows[bsz][1]+tpows[bsz][3])+a.f[3]*(tpows[bsz][1]);
		return c;
	} 
	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, int value) {	// set value at position p
		p+=n;
		seg[p].f = {mi(value+1), 0, 0, 0};
		if(value >= 1){
			seg[p].f[0]-=1;
			seg[p].f[1]+=1;
		}
		if(value >= 3){
			seg[p].f[0]-=1;
			seg[p].f[2]+=1;
		}
		if(value == 1){
			seg[p].s = {0, 1, 0, 1};
		}
		else if(value == 3){
			seg[p].s = {0, 0, 1, 1};
		}
		else{
			seg[p].s = {0, 0, 0, 1};
		}
		
		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);
	}
};
Seg tre;
int main() {
	setIO();
    // you should actually read the stuff at the bottom
    tpows[1][0] = 8;
    tpows[1][1] = 1;
    tpows[1][2] = 1;
    tpows[1][3] = 0;
    for(int i = 2; i < 100005; i++){
    	//make first thing non1, non3
    	tpows[i][0]+=8*(tpows[i-1][0]+tpows[i-1][2]);
    	tpows[i][1]+=8*(tpows[i-1][1]+tpows[i-1][3]);
    	//make first thing 1
    	tpows[i][0]+=tpows[i-1][0];
    	tpows[i][1]+=tpows[i-1][1];
    	//make first thing 3
    	tpows[i][2]+=tpows[i-1][0]+tpows[i-1][2];
    	tpows[i][3]+=tpows[i-1][1]+tpows[i-1][3];
    }
    int N, Q;
    cin >> N >> Q;
    tre.init(N+5);
    string X;
    cin >> X;
    
    for(int i = 1; i <= sz(X); i++){
    	tre.upd(i, X[i-1]-'0');
    }
    T c;
    mi ans;
    c = tre.query(1, N);
    ans = c.f[0]+c.f[1]+c.f[2]+c.f[3];
    ps(int(ans));
    for(int i = 0; i < Q; i++){
    	int t;
    	cin >> t;
    	if(t == 1){
    		int radixL, radixR;
    		cin >> radixL >> radixR;
    		c = tre.query(radixL, radixR);
    		ans = c.f[0]+c.f[1]+c.f[2]+c.f[3];
    		ps(int(ans));
    	}
    	else{
    		int radix, newDigit;
    		cin >> radix >> newDigit;
    		tre.upd(radix, newDigit);
    	}
    }
}
 
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?), set tle
	* do smth instead of nothing and stay organized
*/

Compilation message

lucky.cpp: In function 'void io::setIn(std::__cxx11::string)':
lucky.cpp:135:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
lucky.cpp: In function 'void io::setOut(std::__cxx11::string)':
lucky.cpp:136:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1912 KB Output is correct
2 Correct 9 ms 1912 KB Output is correct
3 Correct 9 ms 1912 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1912 KB Output is correct
2 Correct 9 ms 1912 KB Output is correct
3 Correct 9 ms 1912 KB Output is correct
4 Correct 8 ms 1912 KB Output is correct
5 Correct 8 ms 1912 KB Output is correct
6 Correct 8 ms 1912 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2552 KB Output is correct
2 Correct 21 ms 2812 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2552 KB Output is correct
2 Correct 21 ms 2812 KB Output is correct
3 Correct 59 ms 7416 KB Output is correct
4 Correct 56 ms 7416 KB Output is correct
5 Correct 66 ms 8056 KB Output is correct
6 Correct 79 ms 8824 KB Output is correct
7 Correct 72 ms 8824 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1912 KB Output is correct
2 Correct 9 ms 1912 KB Output is correct
3 Correct 9 ms 1912 KB Output is correct
4 Correct 8 ms 1912 KB Output is correct
5 Correct 8 ms 1912 KB Output is correct
6 Correct 8 ms 1912 KB Output is correct
7 Correct 19 ms 2552 KB Output is correct
8 Correct 21 ms 2812 KB Output is correct
9 Correct 19 ms 2552 KB Output is correct
10 Correct 22 ms 2680 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1912 KB Output is correct
2 Correct 9 ms 1912 KB Output is correct
3 Correct 9 ms 1912 KB Output is correct
4 Correct 8 ms 1912 KB Output is correct
5 Correct 8 ms 1912 KB Output is correct
6 Correct 8 ms 1912 KB Output is correct
7 Correct 19 ms 2552 KB Output is correct
8 Correct 21 ms 2812 KB Output is correct
9 Correct 59 ms 7416 KB Output is correct
10 Correct 56 ms 7416 KB Output is correct
11 Correct 66 ms 8056 KB Output is correct
12 Correct 79 ms 8824 KB Output is correct
13 Correct 72 ms 8824 KB Output is correct
14 Correct 19 ms 2552 KB Output is correct
15 Correct 22 ms 2680 KB Output is correct
16 Correct 59 ms 7416 KB Output is correct
17 Correct 57 ms 7420 KB Output is correct
18 Correct 62 ms 8056 KB Output is correct
19 Correct 77 ms 8660 KB Output is correct
20 Correct 69 ms 8696 KB Output is correct