| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 480198 |
2021-10-15T08:29:09 Z |
deuslovelt |
빨간 직사각형 (kriii3_QQ) |
C++17 |
|
5 ms |
332 KB |
//================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
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)
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
