Submission #480198

#	Time	Username	Problem	Language	Result	Execution time	Memory
480198		deuslovelt	빨간 직사각형 (kriii3_QQ)	C++17	0 / 20	5 ms	332 KiB

qq

//================code===================//


#define TLE
#ifdef TLE
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#endif

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <ctime>
#include <random>
#include <chrono>
#include <stdint.h>


#define ci(t) cin>>t
#define co(t) cout<<t
#define LL long long
#define ld long double
#define fa(i,a,b) for(int i=a;i<b;++i)
#define fd(i,a,b) for(int i=a;i>b;--i)
#define setp tuple<LL,LL,LL>
#define setl pair<LL,LL>
#define seti pair<int,int>
#define VL vector<LL>
#define VI vector<int>
#define eps 0.000000001

using namespace std;


LL gcd(LL a, LL b)
{
	if (!(a && b)) return max(a, b);
	return a % b ? gcd(b, a % b) : b;
}

#ifdef OHSOLUTION
#define ce(t) cerr<<t
#define AT cerr << "\n=================ANS=================\n"
#define AE cerr << "\n=====================================\n"
#define DB(a) cerr << __LINE__ << ": " << #a << " = " << (a) << endl;
#define __builtin_popcount __popcnt
#define __builtin_popcountll __popcnt64
#define LLL LL
#include <intrin.h>
#else
#define AT
#define AE
#define ce(t)
#define DB(a)
#define LLL __int128

#endif

pair <int, int> vu[9] = { {0,1},{1,0},{-1,0} ,{0,-1},{1,1}, {1,-1} , {-1,1},{-1,-1},{0,0} }; //RDLU EWSN
//mt19937 rng((unsigned int)chrono::steady_clock::now().time_since_epoch().count());


template<typename T, typename U> void ckmax(T& a, U b) { a = a < b ? b : a; }
template<typename T, typename U> void ckmin(T& a, U b) { a = a > b ? b : a; }
struct gcmp { bool operator()(LL a, LL b) { return a < b; } bool operator()(setl& a, setl& b) { return a.second < b.second; } };
struct lcmp { bool operator()(LL a, LL b) { return a > b; } bool operator()(setl& a, setl& b) { return a.second > b.second; } };

const int max_v = 3e3 + 7;
const int max_k = 5e2 + 7;
const int bsz = 27;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const LL mod = 1e9 + 7;//998244353;// 
template<typename T, typename U> void MOD(T& a, U b) { a += b; if (a >= mod) a -= mod; };

bitset<max_v> arr[max_v];
struct node
{
	LL dv;
	LL lv;
	LL rv;
	int sz;
};

node seg[max_v << 1];

inline char gc() { // like getchar()
	static char buf[1 << 16];
	static size_t bc, be;
	if (bc >= be) {
		buf[0] = 0, bc = 0;
		be = fread(buf, 1, sizeof(buf), stdin);
	}
	return buf[bc++]; // returns 0 on EOF
}

int main()
{
#ifdef OHSOLUTION
	freopen("input.txt", "r", stdin);
#endif	
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int h,w; ci(h>>w);
	gc();
	fa(i, 0, h)
	{
		fa(j, 0, w) arr[i][j] = gc() == 'R';
		gc();
	}

	LL ans = 0;

	int sz = 1;
	while (sz < w) sz <<= 1;	
	
	auto merge = [&](node& l, node& r, node& ret)
	{
		ret.dv = l.dv + r.dv + l.rv * r.lv;
		ret.lv = (l.lv == l.sz ? l.lv + r.lv : l.lv);
		ret.rv = (r.rv == r.sz ? r.rv + l.rv : r.rv);
		ret.sz = l.sz + r.sz;
	};


	auto update = [&](int i, int v)
	{	
		//ce("upd " << i << " " << v << "\n");
		for (seg[i += sz] = { v,v,v,1 }; i >>= 1;) merge(seg[i << 1], seg[i << 1 | 1], seg[i]);
	};

	
	auto pp = [&](node & T,int idx)
	{
		AT;
		co(idx<< " : ");
		co(T.dv << " " << T.lv << " " << T.rv << " " << T.sz << "\n");
		AE;
	};
	
	auto ffd = [&](bitset<max_v> & bit)
	{
		fa(i, 0, max_v) if (bit[i]) return i;
	};
	
	auto upd = [&](bitset<max_v> bit)
	{
		fa(i,0,w) if(bit[i]) update(i, 0);
	};

	auto build = [&](bitset<max_v>& bit)
	{
		fa(i, 0, w) seg[i + sz] = { bit[i],bit[i],bit[i],1 };
		fd(i, sz - 1, 0) merge(seg[i << 1], seg[i << 1 | 1], seg[i]);
	};

	fa(i, 0, h)
	{
		bitset<max_v> cur = arr[i];		
		build(cur);
		ans += seg[1].dv;

		//co(i << " " << i << " " << seg[1].dv << "\n");

		fa(j, i + 1, h)
		{
			upd((cur & arr[j]) ^ cur);
			ans += seg[1].dv;			
			cur &= arr[j];
			//co(i << " " << j << " " << seg[1].dv << "\n");
		}		
	}

	co(ans);
	return 0;
}

Compilation message (stderr)

qq.cpp: In function 'int main()':
qq.cpp:136:7: warning: variable 'pp' set but not used [-Wunused-but-set-variable]
  136 |  auto pp = [&](node & T,int idx)
      |       ^~
qq.cpp:144:7: warning: variable 'ffd' set but not used [-Wunused-but-set-variable]
  144 |  auto ffd = [&](bitset<max_v> & bit)
      |       ^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10