Skip to content

Instantly share code, notes, and snippets.

@sslotin

sslotin/sse-cf.cpp

Created July 24, 2019 13:28
Show Gist options
  • Save sslotin/de9027f18f8794e95261a2586ab9ad2d to your computer and use it in GitHub Desktop.
Save sslotin/de9027f18f8794e95261a2586ab9ad2d to your computer and use it in GitHub Desktop.
Download ZIP
Raw
sse-cf.cpp
Submission ID: 12760323
-----------------------
#include <iostream>
#include <algorithm>
#include <stdint.h>
#include <nmmintrin.h>
using namespace std;
#ifdef _MSC_VER
#define ALIGN(x) __declspec(align(x))
#else
#define ALIGN(x) __attribute__((aligned(x)))
#endif
static const int64_t INF = (1ll << 62);
static ALIGN(16) int32_t a[100000];
static ALIGN(16) int64_t dp[2][100008];
int main(){
ios_base::sync_with_stdio(false);
int n;
cin >> n;
for(int i = 0; i < n; ++i){ cin >> a[i]; }
for(int i = 0; i <= n; ++i){
dp[0][i] = dp[1][i] = -INF;
}
dp[0][0] = 0;
const __m128i v_four = _mm_set1_epi32(4);
for(int i = 0; i < n; ++i){
const int cur = i & 1, next = 1 - cur;
const int64_t *cur_row = &(dp[cur][0]);
const int64_t ai = a[i];
ALIGN(16) int64_t a_ai[2] = { a[i], a[i] };
ALIGN(16) int64_t a_ai2[2] = { a[i] * 2, a[i] * 2 };
const __m128i v_ai = _mm_load_si128((const __m128i *)a_ai);
const __m128i v_ai2 = _mm_load_si128((const __m128i *)a_ai2);
int64_t *next_row = &(dp[next][0]);
next_row[0] = cur_row[0];
next_row[1] = max(cur_row[0] + ai * 1, cur_row[1]);
next_row[2] = max(cur_row[1] + ai * 2, cur_row[2]);
next_row[3] = max(cur_row[2] + ai * 3, cur_row[3]);
const int last = i + 2;
ALIGN(16) int64_t a_aij_init[2] = { ai * 4, ai * 5 };
__m128i v_aij = _mm_load_si128((const __m128i *)a_aij_init);
__m128i v_prev = _mm_load_si128((const __m128i *)(cur_row + 2));
for(int j = 4; j < last; j += 4){
const __m128i v_c01 = _mm_load_si128((const __m128i *)(cur_row + j));
const __m128i v_c23 = _mm_load_si128((const __m128i *)(cur_row + j + 2));
const __m128i v_m01 = v_aij;
const __m128i v_m23 = _mm_add_epi32(v_aij, v_ai2);
const __m128i v_p01 = _mm_alignr_epi8(v_c01, v_prev, 8);
const __m128i v_p23 = _mm_alignr_epi8(v_c23, v_c01, 8);
const __m128i v_d01 = _mm_add_epi64(v_m01, v_p01);
const __m128i v_d23 = _mm_add_epi64(v_m23, v_p23);
const __m128i v_k01 = _mm_cmpgt_epi64(v_c01, v_d01);
const __m128i v_k23 = _mm_cmpgt_epi64(v_c23, v_d23);
const __m128i v_r01 = _mm_blendv_epi8(v_d01, v_c01, v_k01);
const __m128i v_r23 = _mm_blendv_epi8(v_d23, v_c23, v_k23);
_mm_store_si128((__m128i *)(next_row + j), v_r01);
_mm_store_si128((__m128i *)(next_row + j + 2), v_r23);
v_aij = _mm_add_epi64(v_m23, v_ai2);
v_prev = v_c23;
}
}
int64_t answer = 0;
for(int i = 0; i <= n; ++i){
answer = max(answer, dp[n & 1][i]);
}
cout << answer << endl;
return 0;
}
Submission ID: 12760770
-----------------------
#include <iostream>
#include <algorithm>
#include <stdint.h>
#include <nmmintrin.h>
using namespace std;
#ifdef _MSC_VER
#define ALIGN(x) __declspec(align(x))
#else
#define ALIGN(x) __attribute__((aligned(x)))
#endif
static const int64_t INF = (1ll << 62);
static ALIGN(16) int32_t a[100000];
static ALIGN(16) int64_t dp[2][100008];
int main(){
ios_base::sync_with_stdio(false);
int n;
cin >> n;
for(int i = 0; i < n; ++i){ cin >> a[i]; }
for(int i = 0; i <= n; ++i){
dp[0][i] = dp[1][i] = -INF;
}
dp[0][0] = 0;
for(int i = 0; i < n; ++i){
const int cur = i & 1, next = 1 - cur;
const int64_t *cur_row = &(dp[cur][0]);
const int64_t ai = a[i];
ALIGN(16) int64_t a_ai2[2] = { a[i] * 2, a[i] * 2 };
const __m128i v_ai2 = _mm_load_si128((const __m128i *)a_ai2);
int64_t *next_row = &(dp[next][0]);
next_row[0] = cur_row[0];
next_row[1] = max(cur_row[0] + ai * 1, cur_row[1]);
next_row[2] = max(cur_row[1] + ai * 2, cur_row[2]);
next_row[3] = max(cur_row[2] + ai * 3, cur_row[3]);
const int last = i + 2;
ALIGN(16) int64_t a_aij_init[2] = { ai * 4, ai * 5 };
__m128i v_aij = _mm_load_si128((const __m128i *)a_aij_init);
__m128i v_prev = _mm_load_si128((const __m128i *)(cur_row + 2));
for(int j = 4; j < last; j += 4){
const __m128i v_c01 = _mm_load_si128((const __m128i *)(cur_row + j));
const __m128i v_c23 = _mm_load_si128((const __m128i *)(cur_row + j + 2));
const __m128i v_m01 = v_aij;
const __m128i v_m23 = _mm_add_epi64(v_aij, v_ai2);
const __m128i v_p01 = _mm_alignr_epi8(v_c01, v_prev, 8);
const __m128i v_p23 = _mm_alignr_epi8(v_c23, v_c01, 8);
const __m128i v_d01 = _mm_add_epi64(v_m01, v_p01);
const __m128i v_d23 = _mm_add_epi64(v_m23, v_p23);
const __m128i v_k01 = _mm_cmpgt_epi64(v_c01, v_d01);
const __m128i v_k23 = _mm_cmpgt_epi64(v_c23, v_d23);
const __m128i v_r01 = _mm_blendv_epi8(v_d01, v_c01, v_k01);
const __m128i v_r23 = _mm_blendv_epi8(v_d23, v_c23, v_k23);
_mm_store_si128((__m128i *)(next_row + j), v_r01);
_mm_store_si128((__m128i *)(next_row + j + 2), v_r23);
v_aij = _mm_add_epi64(v_m23, v_ai2);
v_prev = v_c23;
}
}
int64_t answer = 0;
for(int i = 0; i <= n; ++i){
answer = max(answer, dp[n & 1][i]);
}
cout << answer << endl;
return 0;
}
Submission ID: 12766685
-----------------------
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <nmmintrin.h>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
struct Xor128 {
unsigned x, y, z, w;
Xor128(): x(123456789), y(362436069), z(521288629), w(88675123) { }
//[0, 2^32)
unsigned operator()() {
unsigned t = x ^ (x << 11);
x = y; y = z; z = w;
return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}
//[0, 2^64)
unsigned long long nextLL() {
unsigned x = (*this)();
unsigned y = (*this)();
return (unsigned long long)x << 32 | y;
}
//[0, n)
unsigned operator()(unsigned n) {
unsigned mask = calculateMask(n - 1), x;
do {
x = (*this)() & mask;
}while(x >= n);
return x;
}
//[0, n)
signed int operator()(signed int n) { return (*this)((unsigned int)n); }
//[L, U]
signed int operator()(signed int L, signed int U) {
return L + (*this)(U - L + 1);
}
//[0, n)
unsigned long long operator()(unsigned long long n) {
unsigned long long mask = calculateMask(n - 1), x;
do {
x = (*this).nextLL() & mask;
}while(x >= n);
return x;
}
//[0, n)
signed long long operator()(signed long long n) { return (*this)((unsigned long long)n); }
//[L, U]
signed long long operator()(signed long long L, signed long long U) {
return L + (*this)(U - L + 1);
}
private:
static unsigned calculateMask(unsigned v) {
v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16;
return v;
}
static unsigned long long calculateMask(unsigned long long v) {
v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16;
v |= v >> 32;
return v;
}
};
__declspec(noinline) void __cdecl solve(long long *dp, const int *a, int n) {
rep(i, n) {
int t = a[i];
int j = i;
ll ttt[2] = { t * 2, t * 2 };
__m128i tt = _mm_loadu_si128((const __m128i*)ttt);
ll u[2] = { (ll)t * i, (ll)t * (i+1) };
__m128i c = _mm_loadu_si128((const __m128i*)u);
for(; j >= 1; j -= 2) {
__m128i a = _mm_loadu_si128((const __m128i*)(dp + (j-1)));
__m128i x = _mm_add_epi64(a, c);
__m128i y = _mm_loadu_si128((const __m128i*)(dp + j));
__m128i mask = _mm_cmpgt_epi64(y, x);
__m128i z = _mm_blendv_epi8(x, y, mask);
_mm_storeu_si128((__m128i*)(dp + j), z);
c = _mm_sub_epi64(c, tt);
}
for(; j >= 0; -- j)
amax(dp[j+1], dp[j] + (ll)t * (j+1));
}
}
int main(int argc, char **argv) {
Xor128 xor128;
int n;
while(~scanf("%d", &n)) {
vi a(n);
rep(i, n) {
scanf("%d", &a[i]);
// a[i] = xor128((int)-1e7, (int)1e7);
}
long long *dp = new long long[n + 2];
rep(i, n+2) dp[i] = -INFL;
dp[0] = 0;
solve(dp, &a[0], n);
long long ans = *max_element(dp, dp + (n+1));
cout << ans << endl;
}
return 0;
}
Submission ID: 12766903
-----------------------
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#ifdef MY_LOCAL_RUN
#include <nmmintrin.h>
#endif
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
#ifdef MY_LOCAL_RUN
__declspec(noinline) void __cdecl solve(long long *dp, const int *a, int n) {
rep(i, n) {
int t = a[i];
int j = i;
ll ttt[2] = { t * 2, t * 2 };
__m128i tt = _mm_loadu_si128((const __m128i*)ttt);
ll u[2] = { (ll)t * i, (ll)t * (i+1) };
__m128i c = _mm_loadu_si128((const __m128i*)u);
for(; j >= 1; j -= 2) {
__m128i a = _mm_loadu_si128((const __m128i*)(dp + (j-1)));
__m128i x = _mm_add_epi64(a, c);
__m128i y = _mm_loadu_si128((const __m128i*)(dp + j));
__m128i mask = _mm_cmpgt_epi64(y, x);
__m128i z = _mm_blendv_epi8(x, y, mask);
_mm_storeu_si128((__m128i*)(dp + j), z);
c = _mm_sub_epi64(c, tt);
}
for(; j >= 0; -- j)
amax(dp[j+1], dp[j] + (ll)t * (j+1));
}
}
#else
__declspec(noinline) void __cdecl solve(long long *dp, const int *a, int n) {
__asm(
"L99FB2809:\n"
" \n"
" pushl %ebp\n"
" \n"
" \n"
" pushl %edi\n"
" \n"
" \n"
" pushl %esi\n"
" \n"
" \n"
" pushl %ebx\n"
" \n"
" \n"
" subl $64, %esp\n"
" \n"
" movl 92(%esp), %eax\n"
" movl 84(%esp), %edi\n"
" testl %eax, %eax\n"
" jle L992\n"
" leal -8(%edi), %eax\n"
" xorl %ebp, %ebp\n"
" movl %eax, 12(%esp)\n"
" movl $0, 4(%esp)\n"
" movl $0, 8(%esp)\n"
" .p2align 4,,7\n"
"L9911:\n"
" movl 88(%esp), %eax\n"
" movl 8(%esp), %esi\n"
" movl %ebp, 16(%esp)\n"
" movl (%eax,%ebp,4), %eax\n"
" leal (%eax,%eax), %ecx\n"
" movl %eax, %edx\n"
" movl %ecx, %ebx\n"
" sarl $31, %ebx\n"
" movl %ecx, 20(%esp)\n"
" imull %edx, %esi\n"
" movl %ebx, 24(%esp)\n"
" movl %ecx, 28(%esp)\n"
" movl %eax, %ecx\n"
" movl %ebx, 32(%esp)\n"
" movl %eax, %ebx\n"
" movl 4(%esp), %eax\n"
" sarl $31, %ebx\n"
" movdqu 20(%esp), %xmm4\n"
" movl %edx, (%esp)\n"
" imull %ebx, %eax\n"
" leal (%eax,%esi), %esi\n"
" movl (%esp), %eax\n"
" mull 4(%esp)\n"
" addl %esi, %edx\n"
" movl %eax, 36(%esp)\n"
" movl 4(%esp), %eax\n"
" movl %edx, 40(%esp)\n"
" movl 8(%esp), %edx\n"
" addl $1, %eax\n"
" adcl $0, %edx\n"
" movl %eax, %esi\n"
" movl %edx, 8(%esp)\n"
" movl 8(%esp), %edx\n"
" imull %ebx, %esi\n"
" imull (%esp), %edx\n"
" movl %eax, 4(%esp)\n"
" movl (%esp), %eax\n"
" leal (%esi,%edx), %esi\n"
" mull 4(%esp)\n"
" addl %esi, %edx\n"
" testl %ebp, %ebp\n"
" movl %eax, 44(%esp)\n"
" movl %edx, 48(%esp)\n"
" movdqu 36(%esp), %xmm1\n"
" je L994\n"
" movl 12(%esp), %eax\n"
" movl %ebp, %esi\n"
" .p2align 4,,7\n"
"L996:\n"
" movdqu (%eax), %xmm2\n"
" subl $2, %esi\n"
" paddq %xmm1, %xmm2\n"
" movdqu 8(%eax), %xmm3\n"
" subl $16, %eax\n"
" movdqa %xmm3, %xmm0\n"
" pcmpgtq %xmm2, %xmm0\n"
" pblendvb %xmm0, %xmm3, %xmm2\n"
" movdqu %xmm2, 24(%eax)\n"
" testl %esi, %esi\n"
" psubq %xmm4, %xmm1\n"
" jg L996\n"
" leal -1(%ebp), %eax\n"
" andl $-2, %eax\n"
" leal -2(%ebp), %edx\n"
" cmpl %eax, %edx\n"
" jne L997\n"
"L994:\n"
" movl %ecx, %eax\n"
" movl %ebx, %edx\n"
" addl (%edi), %eax\n"
" adcl 4(%edi), %edx\n"
" cmpl 12(%edi), %edx\n"
" jge L9918\n"
"L997:\n"
" addl $1, %ebp\n"
" addl $8, 12(%esp)\n"
" cmpl 92(%esp), %ebp\n"
" jne L9911\n"
"L992:\n"
" addl $64, %esp\n"
" \n"
" \n"
" popl %ebx\n"
" \n"
" \n"
" popl %esi\n"
" \n"
" \n"
" popl %edi\n"
" \n"
" \n"
" popl %ebp\n"
" \n"
" \n"
" ret\n"
" .p2align 4,,7\n"
"L9918:\n"
" \n"
" jg L9912\n"
" cmpl 8(%edi), %eax\n"
" .p2align 4,,2\n"
" jbe L997\n"
"L9912:\n"
" movl %eax, 8(%edi)\n"
" movl %edx, 12(%edi)\n"
" .p2align 4,,2\n"
" jmp L997\n"
" \n"
"\n"
);
}
#endif
int main(int argc, char **argv) {
int n;
while(~scanf("%d", &n)) {
vi a(n);
rep(i, n) {
scanf("%d", &a[i]);
}
long long *dp = new long long[n + 2];
rep(i, n+2) dp[i] = -INFL;
dp[0] = 0;
solve(dp, &a[0], n);
long long ans = *max_element(dp, dp + (n+1));
cout << ans << endl;
}
return 0;
}
Submission ID: 12869848
-----------------------
#pragma GCC target ("mmx,sse,sse2")
#pragma GCC optimize (3)
#include "immintrin.h"
#include <bits/stdc++.h>
using namespace std;
typedef __m128i mi;
#define M(x) _mm_##x##_si128
#define M16(x) _mm_##x##_epi16
#define M32(x) _mm_##x##_epi32
#define rep(i, from, to) for (int i = from; i < int(to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Counter {
int N;
short *xs, *ys, *ups;
Counter() : N(0) {
xs = (short*)_mm_malloc(200000, 32);
ys = (short*)_mm_malloc(200000, 32);
ups = (short*)_mm_malloc(200000, 32);
}
void insert(short x, short y, short len) {
xs[N] = x;
ys[N] = y;
ups[N] = x + y + len;
N++;
}
int count(short x, short y) {
mi mx = M16(set1)(x);
mi my = M16(set1)(y);
mi msum = M16(set1)(x + y);
int ans = 0;
int i = 0;
mi* mxs = (mi*)xs;
mi* mys = (mi*)ys;
mi* mups = (mi*)ups;
int j = 0;
int res = N;
mi mres = M16(set1)(0);
while (i + 8 <= N) {
mi fails = M(or)(
M(or)(
M16(cmplt)(my, mys[j]),
M16(cmplt)(mx, mxs[j])
),
M16(cmplt)(mups[j], msum)
);
mres = M16(add)(mres, fails);
i += 8;
j++;
}
union { unsigned short v[8]; mi m;} u; u.m = mres;
rep(i,0,8)
res -= (int)(unsigned short)-u.v[i];
while (i < N) {
if (!(ys[i] <= y && xs[i] <= x && x + y <= ups[i]))
res--;
++i;
}
return res;
}
};
int main() {
cin.sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
Counter d1, d2, d3, d4;
rep(qi,0,Q) {
short type;
cin >> type;
if (type == 1) {
short dir, x, y, len;
cin >> dir >> x >> y >> len;
#ifdef BENCH
rep(ti,0,10000) {
#endif
if (dir == 1) d1.insert((short)x, (short)y, len);
if (dir == 2) d2.insert((short)x, (short)-y, len);
if (dir == 3) d3.insert((short)-x, (short)y, len);
if (dir == 4) d4.insert((short)-x, (short)-y, len);
#ifdef BENCH
}
#endif
}
else {
assert(type == 2);
short x, y;
cin >> x >> y;
int ans = 0;
#ifdef BENCH
rep(ti,0,10000) {
#endif
ans += d1.count((short)x, (short)y);
ans += d2.count((short)x, (short)-y);
ans += d3.count((short)-x, (short)y);
ans += d4.count((short)-x, (short)-y);
#ifdef BENCH
}
#endif
cout << ans << '\n';
}
}
}
Submission ID: 12873517
-----------------------
#include "xmmintrin.h"
#include <bits/stdc++.h>
using namespace std;
typedef __m128i mi;
#define M(x) _mm_##x##_si128
#define M16(x) _mm_##x##_epi16
#define M32(x) _mm_##x##_epi32
#define rep(i, from, to) for (int i = from; i < int(to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Counter {
int N;
short *xs, *ys, *ups;
Counter() : N(0) {
xs = (short*)_mm_malloc(200000, 32);
ys = (short*)_mm_malloc(200000, 32);
ups = (short*)_mm_malloc(200000, 32);
}
void insert(short x, short y, short len) {
xs[N] = x;
ys[N] = y;
ups[N] = (short)(x + y + len);
N++;
}
int count(short x, short y) {
mi mx = M16(set1)(x);
mi my = M16(set1)(y);
mi msum = M16(set1)((short)(x + y)), mres = M16(set1)(0);
int i = 0;
while (i + 16 <= N) {
mres = M16(add)(mres, M(or)(
M(or)(
M16(cmplt)(my, *(mi*)&ys[i]),
M16(cmplt)(mx, *(mi*)&xs[i])
),
M16(cmplt)(*(mi*)&ups[i], msum)
));
i += 8;
mres = M16(add)(mres, M(or)(
M(or)(
M16(cmplt)(my, *(mi*)&ys[i]),
M16(cmplt)(mx, *(mi*)&xs[i])
),
M16(cmplt)(*(mi*)&ups[i], msum)
));
i += 8;
}
int res = N;
union { short v[8]; mi m;} u; u.m = mres;
rep(i,0,8) res += u.v[i];
while (i < N) {
if (!(ys[i] <= y && xs[i] <= x && x + y <= ups[i]))
res--;
++i;
}
return res;
}
};
int main() {
cin.sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
Counter d1, d2, d3, d4;
rep(qi,0,Q) {
short type;
cin >> type;
if (type == 1) {
short dir, x, y, len;
cin >> dir >> x >> y >> len;
if (dir == 1) d1.insert((short)x, (short)y, len);
if (dir == 2) d2.insert((short)x, (short)-y, len);
if (dir == 3) d3.insert((short)-x, (short)y, len);
if (dir == 4) d4.insert((short)-x, (short)-y, len);
}
else {
assert(type == 2);
short x, y;
cin >> x >> y;
int ans = 0;
ans += d1.count((short)x, (short)y);
ans += d2.count((short)x, (short)-y);
ans += d3.count((short)-x, (short)y);
ans += d4.count((short)-x, (short)-y);
cout << ans << '\n';
}
}
}
Submission ID: 12873525
-----------------------
#include "immintrin.h"
#include <bits/stdc++.h>
using namespace std;
typedef __m128i mi;
#define M(x) _mm_##x##_si128
#define M16(x) _mm_##x##_epi16
#define M32(x) _mm_##x##_epi32
#define rep(i, from, to) for (int i = from; i < int(to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Counter {
int N;
short *xs, *ys, *ups;
Counter() : N(0) {
xs = (short*)_mm_malloc(200000, 32);
ys = (short*)_mm_malloc(200000, 32);
ups = (short*)_mm_malloc(200000, 32);
}
void insert(short x, short y, short len) {
xs[N] = x;
ys[N] = y;
ups[N] = (short)(x + y + len);
N++;
}
int count(short x, short y) {
mi mx = M16(set1)(x);
mi my = M16(set1)(y);
mi msum = M16(set1)((short)(x + y)), mres = M16(set1)(0);
int i = 0;
while (i + 16 <= N) {
mres = M16(add)(mres, M(or)(
M(or)(
M16(cmplt)(my, *(mi*)&ys[i]),
M16(cmplt)(mx, *(mi*)&xs[i])
),
M16(cmplt)(*(mi*)&ups[i], msum)
));
i += 8;
mres = M16(add)(mres, M(or)(
M(or)(
M16(cmplt)(my, *(mi*)&ys[i]),
M16(cmplt)(mx, *(mi*)&xs[i])
),
M16(cmplt)(*(mi*)&ups[i], msum)
));
i += 8;
}
int res = N;
union { short v[8]; mi m;} u; u.m = mres;
rep(i,0,8) res += u.v[i];
while (i < N) {
if (!(ys[i] <= y && xs[i] <= x && x + y <= ups[i]))
res--;
++i;
}
return res;
}
};
int main() {
cin.sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
Counter d1, d2, d3, d4;
rep(qi,0,Q) {
short type;
cin >> type;
if (type == 1) {
short dir, x, y, len;
cin >> dir >> x >> y >> len;
if (dir == 1) d1.insert((short)x, (short)y, len);
if (dir == 2) d2.insert((short)x, (short)-y, len);
if (dir == 3) d3.insert((short)-x, (short)y, len);
if (dir == 4) d4.insert((short)-x, (short)-y, len);
}
else {
assert(type == 2);
short x, y;
cin >> x >> y;
int ans = 0;
ans += d1.count((short)x, (short)y);
ans += d2.count((short)x, (short)-y);
ans += d3.count((short)-x, (short)y);
ans += d4.count((short)-x, (short)-y);
cout << ans << '\n';
}
}
}
Submission ID: 12873533
-----------------------
#pragma GCC target ("mmx,sse,sse2")
#include "xmmintrin.h"
#include <bits/stdc++.h>
using namespace std;
typedef __m128i mi;
#define M(x) _mm_##x##_si128
#define M16(x) _mm_##x##_epi16
#define M32(x) _mm_##x##_epi32
#define rep(i, from, to) for (int i = from; i < int(to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Counter {
int N;
short *xs, *ys, *ups;
Counter() : N(0) {
xs = (short*)_mm_malloc(200000, 32);
ys = (short*)_mm_malloc(200000, 32);
ups = (short*)_mm_malloc(200000, 32);
}
void insert(short x, short y, short len) {
xs[N] = x;
ys[N] = y;
ups[N] = (short)(x + y + len);
N++;
}
int count(short x, short y) {
mi mx = M16(set1)(x);
mi my = M16(set1)(y);
mi msum = M16(set1)((short)(x + y)), mres = M16(set1)(0);
int i = 0;
while (i + 16 <= N) {
mres = M16(add)(mres, M(or)(
M(or)(
M16(cmplt)(my, *(mi*)&ys[i]),
M16(cmplt)(mx, *(mi*)&xs[i])
),
M16(cmplt)(*(mi*)&ups[i], msum)
));
i += 8;
mres = M16(add)(mres, M(or)(
M(or)(
M16(cmplt)(my, *(mi*)&ys[i]),
M16(cmplt)(mx, *(mi*)&xs[i])
),
M16(cmplt)(*(mi*)&ups[i], msum)
));
i += 8;
}
int res = N;
union { short v[8]; mi m;} u; u.m = mres;
rep(i,0,8) res += u.v[i];
while (i < N) {
if (!(ys[i] <= y && xs[i] <= x && x + y <= ups[i]))
res--;
++i;
}
return res;
}
};
int main() {
cin.sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
Counter d1, d2, d3, d4;
rep(qi,0,Q) {
short type;
cin >> type;
if (type == 1) {
short dir, x, y, len;
cin >> dir >> x >> y >> len;
if (dir == 1) d1.insert((short)x, (short)y, len);
if (dir == 2) d2.insert((short)x, (short)-y, len);
if (dir == 3) d3.insert((short)-x, (short)y, len);
if (dir == 4) d4.insert((short)-x, (short)-y, len);
}
else {
assert(type == 2);
short x, y;
cin >> x >> y;
int ans = 0;
ans += d1.count((short)x, (short)y);
ans += d2.count((short)x, (short)-y);
ans += d3.count((short)-x, (short)y);
ans += d4.count((short)-x, (short)-y);
cout << ans << '\n';
}
}
}
Submission ID: 12874991
-----------------------
#pragma GCC target ("mmx,sse,sse2")
//#pragma GCC optimize (3)
#include "immintrin.h"
#include <bits/stdc++.h>
using namespace std;
typedef __m128i mi;
#define M(x) _mm_##x##_si128
#define M16(x) _mm_##x##_epi16
#define M32(x) _mm_##x##_epi32
#define rep(i, from, to) for (int i = from; i < int(to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Counter {
int N;
short *xs, *ys, *ups;
Counter() : N(0) {
xs = (short*)_mm_malloc(200000, 32);
ys = (short*)_mm_malloc(200000, 32);
ups = (short*)_mm_malloc(200000, 32);
}
void insert(short x, short y, short len) {
xs[N] = x;
ys[N] = y;
ups[N] = x + y + len;
N++;
}
int count(short x, short y) {
mi mx = M16(set1)(x);
mi my = M16(set1)(y);
mi msum = M16(set1)(x + y);
int ans = 0;
int i = 0;
mi* mxs = (mi*)xs;
mi* mys = (mi*)ys;
mi* mups = (mi*)ups;
int j = 0;
int res = N;
mi mres = M16(set1)(0);
while (i + 8 <= N) {
mi fails = M(or)(
M(or)(
M16(cmplt)(my, mys[j]),
M16(cmplt)(mx, mxs[j])
),
M16(cmplt)(mups[j], msum)
);
mres = M16(add)(mres, fails);
i += 8;
j++;
}
union { unsigned short v[8]; mi m;} u; u.m = mres;
rep(i,0,8)
res -= (int)(unsigned short)-u.v[i];
while (i < N) {
if (!(ys[i] <= y && xs[i] <= x && x + y <= ups[i]))
res--;
++i;
}
return res;
}
};
int main() {
cin.sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
Counter d1, d2, d3, d4;
rep(qi,0,Q) {
short type;
cin >> type;
if (type == 1) {
short dir, x, y, len;
cin >> dir >> x >> y >> len;
#ifdef BENCH
rep(ti,0,10000) {
#endif
if (dir == 1) d1.insert((short)x, (short)y, len);
if (dir == 2) d2.insert((short)x, (short)-y, len);
if (dir == 3) d3.insert((short)-x, (short)y, len);
if (dir == 4) d4.insert((short)-x, (short)-y, len);
#ifdef BENCH
}
#endif
}
else {
assert(type == 2);
short x, y;
cin >> x >> y;
int ans = 0;
#ifdef BENCH
rep(ti,0,10000) {
#endif
ans += d1.count((short)x, (short)y);
ans += d2.count((short)x, (short)-y);
ans += d3.count((short)-x, (short)y);
ans += d4.count((short)-x, (short)-y);
#ifdef BENCH
}
#endif
cout << ans << '\n';
}
}
}
Submission ID: 12874995
-----------------------
#pragma GCC target ("mmx,sse,sse2")
#pragma GCC optimize (3)
#include "immintrin.h"
#include <bits/stdc++.h>
using namespace std;
typedef __m128i mi;
#define M(x) _mm_##x##_si128
#define M16(x) _mm_##x##_epi16
#define M32(x) _mm_##x##_epi32
#define rep(i, from, to) for (int i = from; i < int(to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Counter {
int N;
short *xs, *ys, *ups;
Counter() : N(0) {
xs = (short*)_mm_malloc(200000, 32);
ys = (short*)_mm_malloc(200000, 32);
ups = (short*)_mm_malloc(200000, 32);
}
void insert(short x, short y, short len) {
xs[N] = x;
ys[N] = y;
ups[N] = x + y + len;
N++;
}
int count(short x, short y) {
mi mx = M16(set1)(x);
mi my = M16(set1)(y);
mi msum = M16(set1)(x + y);
int ans = 0;
int i = 0;
mi* mxs = (mi*)xs;
mi* mys = (mi*)ys;
mi* mups = (mi*)ups;
int j = 0;
int res = N;
mi mres = M16(set1)(0);
while (i + 8 <= N) {
mi fails = M(or)(
M(or)(
M16(cmplt)(my, mys[j]),
M16(cmplt)(mx, mxs[j])
),
M16(cmplt)(mups[j], msum)
);
mres = M16(add)(mres, fails);
i += 8;
j++;
}
union { unsigned short v[8]; mi m;} u; u.m = mres;
rep(i,0,8)
res -= (int)(unsigned short)-u.v[i];
while (i < N) {
if (!(ys[i] <= y && xs[i] <= x && x + y <= ups[i]))
res--;
++i;
}
return res;
}
};
int main() {
cin.sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
Counter d1, d2, d3, d4;
rep(qi,0,Q) {
short type;
cin >> type;
if (type == 1) {
short dir, x, y, len;
cin >> dir >> x >> y >> len;
#ifdef BENCH
rep(ti,0,10000) {
#endif
if (dir == 1) d1.insert((short)x, (short)y, len);
if (dir == 2) d2.insert((short)x, (short)-y, len);
if (dir == 3) d3.insert((short)-x, (short)y, len);
if (dir == 4) d4.insert((short)-x, (short)-y, len);
#ifdef BENCH
}
#endif
}
else {
assert(type == 2);
short x, y;
cin >> x >> y;
int ans = 0;
#ifdef BENCH
rep(ti,0,10000) {
#endif
ans += d1.count((short)x, (short)y);
ans += d2.count((short)x, (short)-y);
ans += d3.count((short)-x, (short)y);
ans += d4.count((short)-x, (short)-y);
#ifdef BENCH
}
#endif
cout << ans << '\n';
}
}
}
Submission ID: 12875000
-----------------------
#pragma GCC target ("mmx,sse,sse2")
#pragma GCC optimize (3)
#include "immintrin.h"
#include <bits/stdc++.h>
using namespace std;
typedef __m128i mi;
#define M(x) _mm_##x##_si128
#define M16(x) _mm_##x##_epi16
#define M32(x) _mm_##x##_epi32
#define rep(i, from, to) for (int i = from; i < int(to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Counter {
int N;
short *xs, *ys, *ups;
Counter() : N(0) {
xs = (short*)_mm_malloc(200000, 32);
ys = (short*)_mm_malloc(200000, 32);
ups = (short*)_mm_malloc(200000, 32);
}
void insert(short x, short y, short len) {
xs[N] = x;
ys[N] = y;
ups[N] = x + y + len;
N++;
}
int count(short x, short y) {
mi mx = M16(set1)(x);
mi my = M16(set1)(y);
mi msum = M16(set1)(x + y);
int ans = 0;
int i = 0;
mi* mxs = (mi*)xs;
mi* mys = (mi*)ys;
mi* mups = (mi*)ups;
int j = 0;
int res = N;
mi mres = M16(set1)(0);
while (i + 8 <= N) {
mi fails = M(or)(
M(or)(
M16(cmplt)(my, mys[j]),
M16(cmplt)(mx, mxs[j])
),
M16(cmplt)(mups[j], msum)
);
mres = M16(add)(mres, fails);
i += 8;
j++;
}
union { unsigned short v[8]; mi m;} u; u.m = mres;
rep(i,0,8)
res -= (int)(unsigned short)-u.v[i];
while (i < N) {
if (!(ys[i] <= y && xs[i] <= x && x + y <= ups[i]))
res--;
++i;
}
return res;
}
};
int main() {
cin.sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
Counter d1, d2, d3, d4;
rep(qi,0,Q) {
short type;
cin >> type;
if (type == 1) {
short dir, x, y, len;
cin >> dir >> x >> y >> len;
#ifdef BENCH
rep(ti,0,10000) {
#endif
if (dir == 1) d1.insert((short)x, (short)y, len);
if (dir == 2) d2.insert((short)x, (short)-y, len);
if (dir == 3) d3.insert((short)-x, (short)y, len);
if (dir == 4) d4.insert((short)-x, (short)-y, len);
#ifdef BENCH
}
#endif
}
else {
assert(type == 2);
short x, y;
cin >> x >> y;
int ans = 0;
#ifdef BENCH
rep(ti,0,10000) {
#endif
ans += d1.count((short)x, (short)y);
ans += d2.count((short)x, (short)-y);
ans += d3.count((short)-x, (short)y);
ans += d4.count((short)-x, (short)-y);
#ifdef BENCH
}
#endif
cout << ans << '\n';
}
}
}
Submission ID: 12875003
-----------------------
#pragma GCC target ("mmx,sse,sse2")
//#pragma GCC optimize (3)
#include "immintrin.h"
#include <bits/stdc++.h>
using namespace std;
typedef __m128i mi;
#define M(x) _mm_##x##_si128
#define M16(x) _mm_##x##_epi16
#define M32(x) _mm_##x##_epi32
#define rep(i, from, to) for (int i = from; i < int(to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Counter {
int N;
short *xs, *ys, *ups;
Counter() : N(0) {
xs = (short*)_mm_malloc(200000, 32);
ys = (short*)_mm_malloc(200000, 32);
ups = (short*)_mm_malloc(200000, 32);
}
void insert(short x, short y, short len) {
xs[N] = x;
ys[N] = y;
ups[N] = x + y + len;
N++;
}
int count(short x, short y) {
mi mx = M16(set1)(x);
mi my = M16(set1)(y);
mi msum = M16(set1)(x + y);
int ans = 0;
int i = 0;
mi* mxs = (mi*)xs;
mi* mys = (mi*)ys;
mi* mups = (mi*)ups;
int j = 0;
int res = N;
mi mres = M16(set1)(0);
while (i + 8 <= N) {
mi fails = M(or)(
M(or)(
M16(cmplt)(my, mys[j]),
M16(cmplt)(mx, mxs[j])
),
M16(cmplt)(mups[j], msum)
);
mres = M16(add)(mres, fails);
i += 8;
j++;
}
union { unsigned short v[8]; mi m;} u; u.m = mres;
rep(i,0,8)
res -= (int)(unsigned short)-u.v[i];
while (i < N) {
if (!(ys[i] <= y && xs[i] <= x && x + y <= ups[i]))
res--;
++i;
}
return res;
}
};
int main() {
cin.sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
Counter d1, d2, d3, d4;
rep(qi,0,Q) {
short type;
cin >> type;
if (type == 1) {
short dir, x, y, len;
cin >> dir >> x >> y >> len;
#ifdef BENCH
rep(ti,0,10000) {
#endif
if (dir == 1) d1.insert((short)x, (short)y, len);
if (dir == 2) d2.insert((short)x, (short)-y, len);
if (dir == 3) d3.insert((short)-x, (short)y, len);
if (dir == 4) d4.insert((short)-x, (short)-y, len);
#ifdef BENCH
}
#endif
}
else {
assert(type == 2);
short x, y;
cin >> x >> y;
int ans = 0;
#ifdef BENCH
rep(ti,0,10000) {
#endif
ans += d1.count((short)x, (short)y);
ans += d2.count((short)x, (short)-y);
ans += d3.count((short)-x, (short)y);
ans += d4.count((short)-x, (short)-y);
#ifdef BENCH
}
#endif
cout << ans << '\n';
}
}
}
Submission ID: 12875015
-----------------------
#pragma GCC target ("mmx,sse,sse2")
#pragma GCC optimize ("O3")
#include "immintrin.h"
#include <bits/stdc++.h>
using namespace std;
typedef __m128i mi;
#define M(x) _mm_##x##_si128
#define M16(x) _mm_##x##_epi16
#define M32(x) _mm_##x##_epi32
#define rep(i, from, to) for (int i = from; i < int(to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Counter {
int N;
short *xs, *ys, *ups;
Counter() : N(0) {
xs = (short*)_mm_malloc(200000, 32);
ys = (short*)_mm_malloc(200000, 32);
ups = (short*)_mm_malloc(200000, 32);
}
void insert(short x, short y, short len) {
xs[N] = x;
ys[N] = y;
ups[N] = x + y + len;
N++;
}
int count(short x, short y) {
mi mx = M16(set1)(x);
mi my = M16(set1)(y);
mi msum = M16(set1)(x + y);
int ans = 0;
int i = 0;
mi* mxs = (mi*)xs;
mi* mys = (mi*)ys;
mi* mups = (mi*)ups;
int j = 0;
int res = N;
mi mres = M16(set1)(0);
while (i + 8 <= N) {
mi fails = M(or)(
M(or)(
M16(cmplt)(my, mys[j]),
M16(cmplt)(mx, mxs[j])
),
M16(cmplt)(mups[j], msum)
);
mres = M16(add)(mres, fails);
i += 8;
j++;
}
union { unsigned short v[8]; mi m;} u; u.m = mres;
rep(i,0,8)
res -= (int)(unsigned short)-u.v[i];
while (i < N) {
if (!(ys[i] <= y && xs[i] <= x && x + y <= ups[i]))
res--;
++i;
}
return res;
}
};
int main() {
cin.sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
Counter d1, d2, d3, d4;
rep(qi,0,Q) {
short type;
cin >> type;
if (type == 1) {
short dir, x, y, len;
cin >> dir >> x >> y >> len;
#ifdef BENCH
rep(ti,0,10000) {
#endif
if (dir == 1) d1.insert((short)x, (short)y, len);
if (dir == 2) d2.insert((short)x, (short)-y, len);
if (dir == 3) d3.insert((short)-x, (short)y, len);
if (dir == 4) d4.insert((short)-x, (short)-y, len);
#ifdef BENCH
}
#endif
}
else {
assert(type == 2);
short x, y;
cin >> x >> y;
int ans = 0;
#ifdef BENCH
rep(ti,0,10000) {
#endif
ans += d1.count((short)x, (short)y);
ans += d2.count((short)x, (short)-y);
ans += d3.count((short)-x, (short)y);
ans += d4.count((short)-x, (short)-y);
#ifdef BENCH
}
#endif
cout << ans << '\n';
}
}
}
Submission ID: 12875035
-----------------------
//#pragma GCC target ("mmx,sse,sse2")
//#pragma GCC optimize ("O3")
#include "immintrin.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <ctime>
#include <cassert>
using namespace std;
typedef __m128i mi;
#define M(x) _mm_##x##_si128
#define M16(x) _mm_##x##_epi16
#define M32(x) _mm_##x##_epi32
#define rep(i, from, to) for (int i = from; i < int(to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Counter {
int N;
short *xs, *ys, *ups;
Counter() : N(0) {
xs = (short*)_mm_malloc(200000, 32);
ys = (short*)_mm_malloc(200000, 32);
ups = (short*)_mm_malloc(200000, 32);
}
void insert(short x, short y, short len) {
xs[N] = x;
ys[N] = y;
ups[N] = x + y + len;
N++;
}
int count(short x, short y) {
mi mx = M16(set1)(x);
mi my = M16(set1)(y);
mi msum = M16(set1)(x + y);
int ans = 0;
int i = 0;
mi* mxs = (mi*)xs;
mi* mys = (mi*)ys;
mi* mups = (mi*)ups;
int j = 0;
int res = N;
mi mres = M16(set1)(0);
while (i + 8 <= N) {
mi fails = M(or)(
M(or)(
M16(cmplt)(my, mys[j]),
M16(cmplt)(mx, mxs[j])
),
M16(cmplt)(mups[j], msum)
);
mres = M16(add)(mres, fails);
i += 8;
j++;
}
union { unsigned short v[8]; mi m;} u; u.m = mres;
rep(i,0,8)
res -= (int)(unsigned short)-u.v[i];
while (i < N) {
if (!(ys[i] <= y && xs[i] <= x && x + y <= ups[i]))
res--;
++i;
}
return res;
}
};
int main() {
cin.sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
Counter d1, d2, d3, d4;
rep(qi,0,Q) {
short type;
cin >> type;
if (type == 1) {
short dir, x, y, len;
cin >> dir >> x >> y >> len;
#ifdef BENCH
rep(ti,0,10000) {
#endif
if (dir == 1) d1.insert((short)x, (short)y, len);
if (dir == 2) d2.insert((short)x, (short)-y, len);
if (dir == 3) d3.insert((short)-x, (short)y, len);
if (dir == 4) d4.insert((short)-x, (short)-y, len);
#ifdef BENCH
}
#endif
}
else {
assert(type == 2);
short x, y;
cin >> x >> y;
int ans = 0;
#ifdef BENCH
rep(ti,0,10000) {
#endif
ans += d1.count((short)x, (short)y);
ans += d2.count((short)x, (short)-y);
ans += d3.count((short)-x, (short)y);
ans += d4.count((short)-x, (short)-y);
#ifdef BENCH
}
#endif
cout << ans << '\n';
}
}
}
Submission ID: 12875038
-----------------------
#pragma GCC target ("mmx,sse,sse2")
//#pragma GCC optimize ("O3")
#include "immintrin.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <ctime>
#include <cassert>
using namespace std;
typedef __m128i mi;
#define M(x) _mm_##x##_si128
#define M16(x) _mm_##x##_epi16
#define M32(x) _mm_##x##_epi32
#define rep(i, from, to) for (int i = from; i < int(to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Counter {
int N;
short *xs, *ys, *ups;
Counter() : N(0) {
xs = (short*)_mm_malloc(200000, 32);
ys = (short*)_mm_malloc(200000, 32);
ups = (short*)_mm_malloc(200000, 32);
}
void insert(short x, short y, short len) {
xs[N] = x;
ys[N] = y;
ups[N] = x + y + len;
N++;
}
int count(short x, short y) {
mi mx = M16(set1)(x);
mi my = M16(set1)(y);
mi msum = M16(set1)(x + y);
int ans = 0;
int i = 0;
mi* mxs = (mi*)xs;
mi* mys = (mi*)ys;
mi* mups = (mi*)ups;
int j = 0;
int res = N;
mi mres = M16(set1)(0);
while (i + 8 <= N) {
mi fails = M(or)(
M(or)(
M16(cmplt)(my, mys[j]),
M16(cmplt)(mx, mxs[j])
),
M16(cmplt)(mups[j], msum)
);
mres = M16(add)(mres, fails);
i += 8;
j++;
}
union { unsigned short v[8]; mi m;} u; u.m = mres;
rep(i,0,8)
res -= (int)(unsigned short)-u.v[i];
while (i < N) {
if (!(ys[i] <= y && xs[i] <= x && x + y <= ups[i]))
res--;
++i;
}
return res;
}
};
int main() {
cin.sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
Counter d1, d2, d3, d4;
rep(qi,0,Q) {
short type;
cin >> type;
if (type == 1) {
short dir, x, y, len;
cin >> dir >> x >> y >> len;
#ifdef BENCH
rep(ti,0,10000) {
#endif
if (dir == 1) d1.insert((short)x, (short)y, len);
if (dir == 2) d2.insert((short)x, (short)-y, len);
if (dir == 3) d3.insert((short)-x, (short)y, len);
if (dir == 4) d4.insert((short)-x, (short)-y, len);
#ifdef BENCH
}
#endif
}
else {
assert(type == 2);
short x, y;
cin >> x >> y;
int ans = 0;
#ifdef BENCH
rep(ti,0,10000) {
#endif
ans += d1.count((short)x, (short)y);
ans += d2.count((short)x, (short)-y);
ans += d3.count((short)-x, (short)y);
ans += d4.count((short)-x, (short)-y);
#ifdef BENCH
}
#endif
cout << ans << '\n';
}
}
}
Submission ID: 12875043
-----------------------
#pragma GCC target ("mmx,sse,sse2")
#pragma GCC optimize (3)
#include "immintrin.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <ctime>
#include <cassert>
using namespace std;
typedef __m128i mi;
#define M(x) _mm_##x##_si128
#define M16(x) _mm_##x##_epi16
#define M32(x) _mm_##x##_epi32
#define rep(i, from, to) for (int i = from; i < int(to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Counter {
int N;
short *xs, *ys, *ups;
Counter() : N(0) {
xs = (short*)_mm_malloc(200000, 32);
ys = (short*)_mm_malloc(200000, 32);
ups = (short*)_mm_malloc(200000, 32);
}
void insert(short x, short y, short len) {
xs[N] = x;
ys[N] = y;
ups[N] = x + y + len;
N++;
}
int count(short x, short y) {
mi mx = M16(set1)(x);
mi my = M16(set1)(y);
mi msum = M16(set1)(x + y);
int ans = 0;
int i = 0;
mi* mxs = (mi*)xs;
mi* mys = (mi*)ys;
mi* mups = (mi*)ups;
int j = 0;
int res = N;
mi mres = M16(set1)(0);
while (i + 8 <= N) {
mi fails = M(or)(
M(or)(
M16(cmplt)(my, mys[j]),
M16(cmplt)(mx, mxs[j])
),
M16(cmplt)(mups[j], msum)
);
mres = M16(add)(mres, fails);
i += 8;
j++;
}
union { unsigned short v[8]; mi m;} u; u.m = mres;
rep(i,0,8)
res -= (int)(unsigned short)-u.v[i];
while (i < N) {
if (!(ys[i] <= y && xs[i] <= x && x + y <= ups[i]))
res--;
++i;
}
return res;
}
};
int main() {
cin.sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
Counter d1, d2, d3, d4;
rep(qi,0,Q) {
short type;
cin >> type;
if (type == 1) {
short dir, x, y, len;
cin >> dir >> x >> y >> len;
#ifdef BENCH
rep(ti,0,10000) {
#endif
if (dir == 1) d1.insert((short)x, (short)y, len);
if (dir == 2) d2.insert((short)x, (short)-y, len);
if (dir == 3) d3.insert((short)-x, (short)y, len);
if (dir == 4) d4.insert((short)-x, (short)-y, len);
#ifdef BENCH
}
#endif
}
else {
assert(type == 2);
short x, y;
cin >> x >> y;
int ans = 0;
#ifdef BENCH
rep(ti,0,10000) {
#endif
ans += d1.count((short)x, (short)y);
ans += d2.count((short)x, (short)-y);
ans += d3.count((short)-x, (short)y);
ans += d4.count((short)-x, (short)-y);
#ifdef BENCH
}
#endif
cout << ans << '\n';
}
}
}
Submission ID: 12875048
-----------------------
#pragma GCC target ("mmx,sse,sse2")
#pragma GCC optimize (3)
#include "immintrin.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <ctime>
#include <cassert>
using namespace std;
typedef __m128i mi;
#define M(x) _mm_##x##_si128
#define M16(x) _mm_##x##_epi16
#define M32(x) _mm_##x##_epi32
#define rep(i, from, to) for (int i = from; i < int(to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Counter {
int N;
short *xs, *ys, *ups;
Counter() : N(0) {
xs = (short*)_mm_malloc(200000, 32);
ys = (short*)_mm_malloc(200000, 32);
ups = (short*)_mm_malloc(200000, 32);
}
void insert(short x, short y, short len) {
xs[N] = x;
ys[N] = y;
ups[N] = x + y + len;
N++;
}
int count(short x, short y) {
mi mx = M16(set1)(x);
mi my = M16(set1)(y);
mi msum = M16(set1)(x + y);
int ans = 0;
int i = 0;
mi* mxs = (mi*)xs;
mi* mys = (mi*)ys;
mi* mups = (mi*)ups;
int j = 0;
int res = N;
mi mres = M16(set1)(0);
while (i + 8 <= N) {
mi fails = M(or)(
M(or)(
M16(cmplt)(my, mys[j]),
M16(cmplt)(mx, mxs[j])
),
M16(cmplt)(mups[j], msum)
);
mres = M16(add)(mres, fails);
i += 8;
j++;
}
union { unsigned short v[8]; mi m;} u; u.m = mres;
rep(i,0,8)
res -= (int)(unsigned short)-u.v[i];
while (i < N) {
if (!(ys[i] <= y && xs[i] <= x && x + y <= ups[i]))
res--;
++i;
}
return res;
}
};
int main() {
cin.sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
Counter d1, d2, d3, d4;
rep(qi,0,Q) {
short type;
cin >> type;
if (type == 1) {
short dir, x, y, len;
cin >> dir >> x >> y >> len;
#ifdef BENCH
rep(ti,0,10000) {
#endif
if (dir == 1) d1.insert((short)x, (short)y, len);
if (dir == 2) d2.insert((short)x, (short)-y, len);
if (dir == 3) d3.insert((short)-x, (short)y, len);
if (dir == 4) d4.insert((short)-x, (short)-y, len);
#ifdef BENCH
}
#endif
}
else {
assert(type == 2);
short x, y;
cin >> x >> y;
int ans = 0;
#ifdef BENCH
rep(ti,0,10000) {
#endif
ans += d1.count((short)x, (short)y);
ans += d2.count((short)x, (short)-y);
ans += d3.count((short)-x, (short)y);
ans += d4.count((short)-x, (short)-y);
#ifdef BENCH
}
#endif
cout << ans << '\n';
}
}
}
Submission ID: 12875050
-----------------------
#pragma GCC target ("mmx,sse,sse2")
//#pragma GCC optimize (3)
#include "immintrin.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <ctime>
#include <cassert>
using namespace std;
typedef __m128i mi;
#define M(x) _mm_##x##_si128
#define M16(x) _mm_##x##_epi16
#define M32(x) _mm_##x##_epi32
#define rep(i, from, to) for (int i = from; i < int(to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Counter {
int N;
short *xs, *ys, *ups;
Counter() : N(0) {
xs = (short*)_mm_malloc(200000, 32);
ys = (short*)_mm_malloc(200000, 32);
ups = (short*)_mm_malloc(200000, 32);
}
void insert(short x, short y, short len) {
xs[N] = x;
ys[N] = y;
ups[N] = x + y + len;
N++;
}
int count(short x, short y) {
mi mx = M16(set1)(x);
mi my = M16(set1)(y);
mi msum = M16(set1)(x + y);
int ans = 0;
int i = 0;
mi* mxs = (mi*)xs;
mi* mys = (mi*)ys;
mi* mups = (mi*)ups;
int j = 0;
int res = N;
mi mres = M16(set1)(0);
while (i + 8 <= N) {
mi fails = M(or)(
M(or)(
M16(cmplt)(my, mys[j]),
M16(cmplt)(mx, mxs[j])
),
M16(cmplt)(mups[j], msum)
);
mres = M16(add)(mres, fails);
i += 8;
j++;
}
union { unsigned short v[8]; mi m;} u; u.m = mres;
rep(i,0,8)
res -= (int)(unsigned short)-u.v[i];
while (i < N) {
if (!(ys[i] <= y && xs[i] <= x && x + y <= ups[i]))
res--;
++i;
}
return res;
}
};
int main() {
cin.sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
Counter d1, d2, d3, d4;
rep(qi,0,Q) {
short type;
cin >> type;
if (type == 1) {
short dir, x, y, len;
cin >> dir >> x >> y >> len;
#ifdef BENCH
rep(ti,0,10000) {
#endif
if (dir == 1) d1.insert((short)x, (short)y, len);
if (dir == 2) d2.insert((short)x, (short)-y, len);
if (dir == 3) d3.insert((short)-x, (short)y, len);
if (dir == 4) d4.insert((short)-x, (short)-y, len);
#ifdef BENCH
}
#endif
}
else {
assert(type == 2);
short x, y;
cin >> x >> y;
int ans = 0;
#ifdef BENCH
rep(ti,0,10000) {
#endif
ans += d1.count((short)x, (short)y);
ans += d2.count((short)x, (short)-y);
ans += d3.count((short)-x, (short)y);
ans += d4.count((short)-x, (short)-y);
#ifdef BENCH
}
#endif
cout << ans << '\n';
}
}
}
Submission ID: 12875052
-----------------------
#pragma GCC target ("mmx,sse,sse2")
// #pragma GCC optimize (3)
#include "immintrin.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <ctime>
#include <cassert>
using namespace std;
typedef __m128i mi;
#define M(x) _mm_##x##_si128
#define M16(x) _mm_##x##_epi16
#define M32(x) _mm_##x##_epi32
#define rep(i, from, to) for (int i = from; i < int(to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Counter {
int N;
short *xs, *ys, *ups;
Counter() : N(0) {
xs = (short*)_mm_malloc(200000, 32);
ys = (short*)_mm_malloc(200000, 32);
ups = (short*)_mm_malloc(200000, 32);
}
void insert(short x, short y, short len) {
xs[N] = x;
ys[N] = y;
ups[N] = x + y + len;
N++;
}
int count(short x, short y) {
mi mx = M16(set1)(x);
mi my = M16(set1)(y);
mi msum = M16(set1)(x + y);
int ans = 0;
int i = 0;
mi* mxs = (mi*)xs;
mi* mys = (mi*)ys;
mi* mups = (mi*)ups;
int j = 0;
int res = N;
mi mres = M16(set1)(0);
while (i + 8 <= N) {
mi fails = M(or)(
M(or)(
M16(cmplt)(my, mys[j]),
M16(cmplt)(mx, mxs[j])
),
M16(cmplt)(mups[j], msum)
);
mres = M16(add)(mres, fails);
i += 8;
j++;
}
union { unsigned short v[8]; mi m;} u; u.m = mres;
rep(i,0,8)
res -= (int)(unsigned short)-u.v[i];
while (i < N) {
if (!(ys[i] <= y && xs[i] <= x && x + y <= ups[i]))
res--;
++i;
}
return res;
}
};
int main() {
cin.sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
Counter d1, d2, d3, d4;
rep(qi,0,Q) {
short type;
cin >> type;
if (type == 1) {
short dir, x, y, len;
cin >> dir >> x >> y >> len;
#ifdef BENCH
rep(ti,0,10000) {
#endif
if (dir == 1) d1.insert((short)x, (short)y, len);
if (dir == 2) d2.insert((short)x, (short)-y, len);
if (dir == 3) d3.insert((short)-x, (short)y, len);
if (dir == 4) d4.insert((short)-x, (short)-y, len);
#ifdef BENCH
}
#endif
}
else {
assert(type == 2);
short x, y;
cin >> x >> y;
int ans = 0;
#ifdef BENCH
rep(ti,0,10000) {
#endif
ans += d1.count((short)x, (short)y);
ans += d2.count((short)x, (short)-y);
ans += d3.count((short)-x, (short)y);
ans += d4.count((short)-x, (short)-y);
#ifdef BENCH
}
#endif
cout << ans << '\n';
}
}
}
Submission ID: 12875142
-----------------------
#pragma GCC target ("mmx,sse,sse2")
// #pragma GCC optimize (3)
#include "immintrin.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <ctime>
#include <cassert>
using namespace std;
typedef __m128i mi;
__m512i haha;
#define M(x) _mm_##x##_si128
#define M16(x) _mm_##x##_epi16
#define M32(x) _mm_##x##_epi32
#define rep(i, from, to) for (int i = from; i < int(to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Counter {
int N;
short *xs, *ys, *ups;
Counter() : N(0) {
xs = (short*)_mm_malloc(200000, 32);
ys = (short*)_mm_malloc(200000, 32);
ups = (short*)_mm_malloc(200000, 32);
}
void insert(short x, short y, short len) {
xs[N] = x;
ys[N] = y;
ups[N] = x + y + len;
N++;
}
int count(short x, short y) {
mi mx = M16(set1)(x);
mi my = M16(set1)(y);
mi msum = M16(set1)(x + y);
int ans = 0;
int i = 0;
mi* mxs = (mi*)xs;
mi* mys = (mi*)ys;
mi* mups = (mi*)ups;
int j = 0;
int res = N;
mi mres = M16(set1)(0);
while (i + 8 <= N) {
mi fails = M(or)(
M(or)(
M16(cmplt)(my, mys[j]),
M16(cmplt)(mx, mxs[j])
),
M16(cmplt)(mups[j], msum)
);
mres = M16(add)(mres, fails);
i += 8;
j++;
}
union { unsigned short v[8]; mi m;} u; u.m = mres;
rep(i,0,8)
res -= (int)(unsigned short)-u.v[i];
while (i < N) {
if (!(ys[i] <= y && xs[i] <= x && x + y <= ups[i]))
res--;
++i;
}
return res;
}
};
int main() {
cin.sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
Counter d1, d2, d3, d4;
rep(qi,0,Q) {
short type;
cin >> type;
if (type == 1) {
short dir, x, y, len;
cin >> dir >> x >> y >> len;
#ifdef BENCH
rep(ti,0,10000) {
#endif
if (dir == 1) d1.insert((short)x, (short)y, len);
if (dir == 2) d2.insert((short)x, (short)-y, len);
if (dir == 3) d3.insert((short)-x, (short)y, len);
if (dir == 4) d4.insert((short)-x, (short)-y, len);
#ifdef BENCH
}
#endif
}
else {
assert(type == 2);
short x, y;
cin >> x >> y;
int ans = 0;
#ifdef BENCH
rep(ti,0,10000) {
#endif
ans += d1.count((short)x, (short)y);
ans += d2.count((short)x, (short)-y);
ans += d3.count((short)-x, (short)y);
ans += d4.count((short)-x, (short)-y);
#ifdef BENCH
}
#endif
cout << ans << '\n';
}
}
}
Submission ID: 12875674
-----------------------
//#pragma GCC target ("mmx,sse,sse2")
#pragma GCC target ("mmx,3dnow,sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,aes,pclmul,xop,popcnt,abm,lwp,avx,avx512f")
// #pragma GCC optimize ("O0")
#include "immintrin.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <ctime>
#include <cassert>
using namespace std;
typedef __m512i mi;
#define M(x) _mm512_##x##_si512
#define M32(x) _mm512_##x##_epi32
#define rep(i, from, to) for (int i = from; i < int(to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Counter {
int N;
int *xs, *ys, *ups;
Counter() : N(0) {
xs = (int*)_mm_malloc(200000, 32);
ys = (int*)_mm_malloc(200000, 32);
ups = (int*)_mm_malloc(200000, 32);
}
void insert(int x, int y, int len) {
xs[N] = x;
ys[N] = y;
ups[N] = x + y + len;
N++;
}
int count(int x, int y) {
mi mx = M32(set1)(x);
mi my = M32(set1)(y);
mi msum = M32(set1)(x + y);
int ans = 0;
int i = 0;
mi* mxs = (mi*)xs;
mi* mys = (mi*)ys;
mi* mups = (mi*)ups;
int j = 0;
int res = N;
mi mres = M32(set1)(0);
mi ones = M32(set1)(1);
while (i + 16 <= N) {
//mi fails = mres;
mi fails = M(or)(
M(or)(
_mm512_maskz_mov_epi32(_mm512_cmplt_epi32_mask(my, mys[j]), ones),
_mm512_maskz_mov_epi32(_mm512_cmplt_epi32_mask(mx, mxs[j]), ones)
),
_mm512_maskz_mov_epi32(_mm512_cmplt_epi32_mask(mups[j], msum), ones)
);
mres = M32(add)(mres, fails);
i += 32;
j++;
}
union { unsigned int v[16]; mi m;} u; u.m = mres;
rep(i,0,16)
res -= (int)(unsigned int)-u.v[i];
while (i < N) {
if (!(ys[i] <= y && xs[i] <= x && x + y <= ups[i]))
res--;
++i;
}
return res;
}
};
int main() {
cin.sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
Counter d1, d2, d3, d4;
rep(qi,0,Q) {
int type;
cin >> type;
if (type == 1) {
int dir, x, y, len;
cin >> dir >> x >> y >> len;
#ifdef BENCH
rep(ti,0,10000) {
#endif
if (dir == 1) d1.insert((int)x, (int)y, len);
if (dir == 2) d2.insert((int)x, (int)-y, len);
if (dir == 3) d3.insert((int)-x, (int)y, len);
if (dir == 4) d4.insert((int)-x, (int)-y, len);
#ifdef BENCH
}
#endif
}
else {
assert(type == 2);
int x, y;
cin >> x >> y;
int ans = 0;
#ifdef BENCH
rep(ti,0,10000) {
#endif
ans += d1.count((int)x, (int)y);
ans += d2.count((int)x, (int)-y);
ans += d3.count((int)-x, (int)y);
ans += d4.count((int)-x, (int)-y);
#ifdef BENCH
}
#endif
cout << ans << '\n';
}
}
}
Submission ID: 12891580
-----------------------
#include<bits/stdc++.h>
using namespace std;
long long MAX = 1000005;
long long fact[1000005];
long long mod = 1000000007;
long long find_mmi(long long base,long long p)
{
if(p == 0)return 1;
long long h = find_mmi(base,p/2);
if(p%2)return ((h*h)%mod * base)%mod;
else return (h*h)%mod;
}
long long func(long long a,long long b)
{
if(a < b)return 0;
return (fact[a]*find_mmi((fact[b]*fact[a-b])%mod,mod-2))%mod;
}
int main()
{
long long n,i;
scanf("%lld",&n);
fact[0] = 1;
for(i=1; i<MAX; i++)
fact[i] = (i*fact[i-1])%mod;
long long ans = 0;
for(i=n; i>=1; i--)
{
ans = (ans + (func(2*i,i) + func(2*i-1,i+1))%mod)%mod;
}
printf("%lld",(2*ans+1)%mod);
return 0;
}
Submission ID: 12891601
-----------------------
#include<bits/stdc++.h>
using namespace std;
long long MAX = 2000005;
long long fact[2000005];
long long mod = 1000000007;
long long find_mmi(long long base,long long p)
{
if(p == 0)return 1;
long long h = find_mmi(base,p/2);
if(p%2)return ((h*h)%mod * base)%mod;
else return (h*h)%mod;
}
long long func(long long a,long long b)
{
if(a < b)return 0;
return (fact[a]*find_mmi((fact[b]*fact[a-b])%mod,mod-2))%mod;
}
int main()
{
long long n,i;
scanf("%lld",&n);
fact[0] = 1;
for(i=1; i<MAX; i++)
fact[i] = (i*fact[i-1])%mod;
long long ans = 0;
for(i=n; i>=1; i--)
{
ans = (ans + (func(2*i,i) + func(2*i-1,i+1))%mod)%mod;
}
printf("%lld",(2*ans+1)%mod);
return 0;
}
Submission ID: 13058236
-----------------------
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 200200;
double a[maxn];
int n;
double calc(double mid)
{
double ret = 0, tmp = 0;
for(int i = 1;i <= n; i ++)
{
tmp += a[i] - mid;
ret = max(ret, tmp);
if(tmp < 0) tmp = 0;
}
tmp = 0;
for(int i = 1;i <= n; i ++)
{
tmp += a[i] - mid;
ret = max(ret, -tmp);
if(tmp > 0) tmp = 0;
}
return ret;
}
void solve()
{
double L = -10000, R = 10000;
for(int cas = 0; cas < 50; cas ++)
{
double mid = (L + R) / 2, mmid = (mid + R) / 2;
double _mid = calc(mid), _mmid = calc(mmid);
if(_mid > _mmid) L = mid;
else R = mmid;
}
printf("%.10f\n", calc((L + R) / 2));
}
int main()
{
while(scanf("%d", &n) != EOF)
{
for(int i = 1; i <= n; i ++)
scanf("%lf", &a[i]);
solve();
}
return 0;
}
Submission ID: 13058258
-----------------------
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 200200;
double a[maxn];
int n;
double calc(double mid)
{
double ret = 0, tmp = 0;
for(int i = 1;i <= n; i ++)
{
tmp += a[i] - mid;
ret = max(ret, tmp);
if(tmp < 0) tmp = 0;
}
tmp = 0;
for(int i = 1;i <= n; i ++)
{
tmp += a[i] - mid;
ret = max(ret, -tmp);
if(tmp > 0) tmp = 0;
}
return ret;
}
void solve()
{
double L = -10000, R = 10000;
for(int cas = 0; cas < 100; cas ++)
{
double mid = (L + R) / 2, mmid = (mid + R) / 2;
double _mid = calc(mid), _mmid = calc(mmid);
if(_mid > _mmid) L = mid;
else R = mmid;
}
// printf("%f -- %f\n", L, R);
printf("%.10f\n", calc((L + R) / 2));
}
int main()
{
while(scanf("%d", &n) != EOF)
{
for(int i = 1; i <= n; i ++)
scanf("%lf", &a[i]);
solve();
}
return 0;
}
Submission ID: 13058284
-----------------------
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 200200;
double a[maxn];
int n;
double calc(double mid)
{
double ret = 0, tmp = 0;
for(int i = 1;i <= n; i ++)
{
tmp += a[i] - mid;
ret = max(ret, tmp);
if(tmp < 0) tmp = 0;
}
tmp = 0;
for(int i = 1;i <= n; i ++)
{
tmp += a[i] - mid;
ret = max(ret, -tmp);
if(tmp > 0) tmp = 0;
}
return ret;
}
void solve()
{
double L = -20000, R = 20000;
for(int cas = 0; cas < 100; cas ++)
{
double mid = (L + R) / 2, mmid = (mid + R) / 2;
double _mid = calc(mid), _mmid = calc(mmid);
if(_mid > _mmid) L = mid;
else R = mmid;
}
// printf("%f -- %f\n", L, R);
printf("%.10f\n", calc((L + R) / 2));
}
int main()
{
while(scanf("%d", &n) != EOF)
{
for(int i = 1; i <= n; i ++)
scanf("%lf", &a[i]);
solve();
}
return 0;
}
Submission ID: 33943467
-----------------------
#include <iostream>
#include <cstdio>
#include<list>
#include<iomanip>
#include<cmath>
#include<queue>
#include <functional>
#include<stdio.h>
#include<assert.h>
#include<stack>
#include<sstream>
#include <cstdlib>
#include<map>
#include<algorithm>
#include<iostream>
#include<set>
#include<utility>
#include<memory.h>
#include<string>
#include<vector>
#include<numeric>
#include <unordered_map>
using namespace std;
#define ll long long
#define pb push_back
#define fi(ss) freopen (ss,"r",stdin)
#define fo(ss) freopen (ss,"w",stdout)
#define sz(v) ((int)((v).size()))
#define all(x) (x).begin(),(x).end()
#define REP(i, v) for(int i=0;i<sz(v);i++)
#define lp(i,n) for(int i = 0 ; i < n ; ++i)
typedef pair<int,int> pii;
#define ios std::ios_base::sync_with_stdio(false);
using namespace std;
int n,m;
typedef long long LL;
set<ll> s;
typedef vector<ll> VL;
const LL MAX = (1LL<<63)-1;
#define FOREACH(it,c) for(typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define MAX(f,w) ({ int _mm=(1<<31); f _mm>?=(w); _mm; })
int main() {
ios
ll k;
cin >> k;
vector<ll> factors(k);
for(int i = 0 ; i < k ;++i) cin >> factors[i];
sort(all(factors));
cin >> n;
s.clear();
s.insert(1);
while(n>0) {
--n;
if(s.empty()) {
assert(false);
}
LL x = *s.begin();
if(n==0) {
cout << x << "\n";
return 0;
}
s.erase(x);
FOREACH(it,factors) {
if(x <= (MAX / *it)) s.insert(1LL*x * *it);
}
while(sz(s)>n) {
set<ll>::iterator it = s.end(); --it;
s.erase(it);
}
}
}
Submission ID: 33943508
-----------------------
#include <iostream>
#include <cstdio>
#include<list>
#include<iomanip>
#include<cmath>
#include<queue>
#include <functional>
#include<stdio.h>
#include<assert.h>
#include<stack>
#include<sstream>
#include <cstdlib>
#include<map>
#include<algorithm>
#include<iostream>
#include<set>
#include<utility>
#include<memory.h>
#include<string>
#include<vector>
#include<numeric>
using namespace std;
#define ll long long
#define pb push_back
#define fi(ss) freopen (ss,"r",stdin)
#define fo(ss) freopen (ss,"w",stdout)
#define sz(v) ((int)((v).size()))
#define all(x) (x).begin(),(x).end()
#define REP(i, v) for(int i=0;i<sz(v);i++)
#define lp(i,n) for(int i = 0 ; i < n ; ++i)
typedef pair<int,int> pii;
#define ios std::ios_base::sync_with_stdio(false);
using namespace std;
int n,m;
typedef long long LL;
set<ll> s;
typedef vector<ll> VL;
const LL MAX = (1LL<<63)-1;
#define FOREACH(it,c) for(typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define MAX(f,w) ({ int _mm=(1<<31); f _mm>?=(w); _mm; })
int main() {
ios
ll k;
cin >> k;
vector<ll> factors(k);
for(int i = 0 ; i < k ;++i) cin >> factors[i];
sort(all(factors));
cin >> n;
s.clear();
s.insert(1);
while(n>0) {
--n;
if(s.empty()) {
assert(false);
}
LL x = *s.begin();
if(n==0) {
cout << x << "\n";
return 0;
}
s.erase(x);
FOREACH(it,factors) {
if(x <= (MAX / *it)) s.insert(1LL*x * *it);
}
while(sz(s)>n) {
set<ll>::iterator it = s.end(); --it;
s.erase(it);
}
}
}
Submission ID: 33943714
-----------------------
#include <iostream>
#include <cstdio>
#include<list>
#include<iomanip>
#include<cmath>
#include<queue>
#include <functional>
#include<stdio.h>
#include<assert.h>
#include<stack>
#include<sstream>
#include <cstdlib>
#include<map>
#include<algorithm>
#include<iostream>
#include<set>
#include<utility>
#include<memory.h>
#include<string>
#include<vector>
#include<numeric>
using namespace std;
#define ll long long
#define pb push_back
#define fi(ss) freopen (ss,"r",stdin)
#define fo(ss) freopen (ss,"w",stdout)
#define sz(v) ((int)((v).size()))
#define all(x) (x).begin(),(x).end()
#define REP(i, v) for(int i=0;i<sz(v);i++)
#define lp(i,n) for(int i = 0 ; i < n ; ++i)
typedef pair<int,int> pii;
#define ios std::ios_base::sync_with_stdio(false);
using namespace std;
int n,m;
typedef long long LL;
set<ll> s;
typedef vector<ll> VL;
const LL MAX = (1LL<<62);
#define FOREACH(it,c) for(typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define MAX(f,w) ({ int _mm=(1<<31); f _mm>?=(w); _mm; })
int main() {
ios
ll k;
cin >> k;
vector<ll> factors(k);
for(int i = 0 ; i < k ;++i) cin >> factors[i];
sort(all(factors));
cin >> n;
s.clear();
s.insert(1);
while(n>0) {
--n;
if(s.empty()) {
assert(false);
}
LL x = *s.begin();
if(n==0) {
cout << x << "\n";
return 0;
}
s.erase(x);
FOREACH(it,factors) {
if(x <= (MAX / *it)) s.insert(1LL*x * *it);
}
while (sz(s) > n ) {
set<ll>::iterator it = s.end(); --it;
s.erase(it);
}
}
}
Submission ID: 33943898
-----------------------
#include <iostream>
#include <cstdio>
#include<list>
#include<iomanip>
#include<cmath>
#include<queue>
#include <functional>
#include<stdio.h>
#include<assert.h>
#include<stack>
#include<sstream>
#include <cstdlib>
#include<map>
#include<algorithm>
#include<iostream>
#include<set>
#include<utility>
#include<memory.h>
#include<string>
#include<vector>
#include<numeric>
using namespace std;
#define ll long long
#define pb push_back
#define fi(ss) freopen (ss,"r",stdin)
#define fo(ss) freopen (ss,"w",stdout)
#define sz(v) ((int)((v).size()))
#define all(x) (x).begin(),(x).end()
#define REP(i, v) for(int i=0;i<sz(v);i++)
#define lp(i,n) for(int i = 0 ; i < n ; ++i)
typedef pair<int,int> pii;
#define ios std::ios_base::sync_with_stdio(false);
using namespace std;
int n,m;
typedef long long LL;
set<ll> s;
typedef vector<ll> VL;
const ll d = 1000*1000*1000LL;
const LL MAX = (d*d);
#define FOREACH(it,c) for(typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define MAX(f,w) ({ int _mm=(1<<31); f _mm>?=(w); _mm; })
int main() {
ios
ll k;
cin >> k;
vector<ll> factors(k);
for(int i = 0 ; i < k ;++i) cin >> factors[i];
sort(all(factors));
cin >> n;
s.clear();
s.insert(1);
while(n>0) {
--n;
if(s.empty()) {
assert(false);
}
LL x = *s.begin();
if(n==0) {
cout << x << "\n";
return 0;
}
s.erase(x);
FOREACH(it,factors) {
if(x <= (MAX / *it)) s.insert(1LL*x * *it);
}
while(sz(s)>n) {
set<ll>::iterator it = s.end(); --it;
s.erase(it);
}
}
}
Submission ID: 33945005
-----------------------
#include <iostream>
#include <cstdio>
#include<list>
#include<iomanip>
#include<cmath>
#include<queue>
#include <functional>
#include<stdio.h>
#include<assert.h>
#include<stack>
#include<sstream>
#include <cstdlib>
#include<map>
#include<algorithm>
#include<iostream>
#include<set>
#include<utility>
#include<memory.h>
#include<string>
#include<vector>
#include<numeric>
using namespace std;
#define ll long long
#define pb push_back
#define fi(ss) freopen (ss,"r",stdin)
#define fo(ss) freopen (ss,"w",stdout)
#define sz(v) ((int)((v).size()))
#define all(x) (x).begin(),(x).end()
#define REP(i, v) for(int i=0;i<sz(v);i++)
#define lp(i,n) for(int i = 0 ; i < n ; ++i)
typedef pair<int,int> pii;
#define ios std::ios_base::sync_with_stdio(false);
using namespace std;
int n,m;
typedef long long LL;
set<ll> s;
typedef vector<ll> VL;
const ll d = 1000*1000*1000LL;
const LL MAX = (d*d);
#define FOREACH(it,c) for(typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define MAX(f,w) ({ int _mm=(1<<31); f _mm>?=(w); _mm; })
int main() {
ios
ll k;
cin >> k;
vector<ll> factors(k);
for(int i = 0 ; i < k ;++i) cin >> factors[i];
sort(all(factors));
cin >> n;
s.clear();
s.insert(1);
while(n>0) {
--n;
if(s.empty()) {
assert(false);
}
LL x = *s.begin();
if(n==0) {
cout << x << "\n";
return 0;
}
s.erase(x);
FOREACH(it,factors) {
if(x * (*it) <= (MAX)) s.insert(1LL*x * *it);
}
while(sz(s)>n) {
set<ll>::iterator it = s.end(); --it;
s.erase(it);
}
}
}
Submission ID: 34056841
-----------------------
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("avx")
#include <iostream>
#include <x86intrin.h>
using namespace std;
constexpr int MAX_N = 1<<18;
constexpr int BUF_SIZE = 16<<20;
char input[BUF_SIZE], output[BUF_SIZE];
int nIn, nOut;
__attribute__((aligned(16))) char elems[MAX_N];
inline __attribute__((always_inline)) int getUint() {
int n = 0, chr = input[nIn++];
while (chr == '\n' || chr == ' ') chr = input[nIn++];
do {
n = n*10 + chr - '0';
chr = input[nIn++];
} while (chr != '\n' && chr != ' ');
return n;
}
inline __attribute__((always_inline)) void putUint(int n) {
char str[10];
int i = 0;
while (n > 0) {
str[i++] = char((n % 10) + '0');
n /= 10;
}
while (--i >= 0) output[nOut++] = str[i];
}
int main() {
cin.sync_with_stdio(0); cin.tie(0);
fread(input, 1, BUF_SIZE, stdin);
__m128i pack, mask, vecX, vecY;
int n, q, l, r, limit;
char x, y;
n = getUint();
for (int i = 0; i < n; i++) elems[i] = char(getUint());
q = getUint();
mainLoop:
while (q--) {
l = getUint()-1;
r = getUint();
x = char(getUint());
y = char(getUint());
constexpr int BLOCK = 16;
constexpr int BLOCK_MASK = BLOCK-1;
limit = r-BLOCK_MASK;
while (l & BLOCK_MASK) {
if (elems[l] == x) elems[l] = y;
if (++l >= r) goto mainLoop;
}
vecX = _mm_set_epi8(x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x);
vecY = _mm_set_epi8(y,y,y,y,y,y,y,y,y,y,y,y,y,y,y,y);
while (l < limit) {
pack = _mm_load_si128((__m128i*)(elems+l));
mask = _mm_cmpeq_epi8(pack, vecX);
_mm_store_si128((__m128i*)(elems+l), _mm_blendv_epi8(pack, vecY, mask));
l += BLOCK;
}
for (; l < r; l++) if (elems[l] == x) elems[l] = y;
}
for (int i = 0; i < n; i++) {
putUint(elems[i]);
output[nOut++] = ' ';
}
output[nOut++] = '\n';
fwrite(output, 1, nOut, stdout);
fflush(stdout);
return 0;
}
Submission ID: 34307561
-----------------------
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <map>
using namespace std;
int main() {
int x;
cin >> x;
int hh, mm;
cin >> hh >> mm;
int cnt = 0;
string str_hh = to_string(hh);
string str_mm = to_string(mm);
bool isSeven = false;
for (int i = 0; i < str_hh.size(); i++) {
if (str_hh.at(i) == '7') {
isSeven = true;
break;
}
}
for (int i = 0; i < str_mm.size(); i++) {
if (str_mm.at(i) == '7') {
isSeven = true;
break;
}
}
if (isSeven) {
cout << cnt;
}
else {
while (true) {
cnt++;
for (int i = 0; i < x; i++) {
mm = (mm + 1) % 60;
hh = (hh + (mm + 1) / 60) % 24;
string str_hh = to_string(hh);
string str_mm = to_string(mm);
for (int j = 0; j < str_hh.size(); j++) {
if (str_hh.at(j) == '7') {
isSeven = true;
break;
}
}
for (int j = 0; j < str_mm.size();j++) {
if (str_mm.at(j) == '7') {
isSeven = true;
break;
}
}
}
if (isSeven) {
break;
}
}
cout << cnt;
}
}
Submission ID: 34308614
-----------------------
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <map>
using namespace std;
int main() {
int x;
cin >> x;
int hh, mm;
cin >> hh >> mm;
int cnt = 0;
string str_hh = to_string(hh);
string str_mm = to_string(mm);
bool isSeven = false;
for (int i = 0; i < str_hh.size(); i++) {
if (str_hh.at(i) == '7') {
isSeven = true;
break;
}
}
for (int i = 0; i < str_mm.size(); i++) {
if (str_mm.at(i) == '7') {
isSeven = true;
break;
}
}
if (isSeven) {
cout << cnt;
}
else {
while (true) {
cnt++;
for (int i = 0; i < x; i++) {
int min = (mm + 1) / 60;
mm = (mm + 1) % 60;
hh = (hh + min) % 24;
string str_hh = to_string(hh);
string str_mm = to_string(mm);
for (int j = 0; j < str_hh.size(); j++) {
if (str_hh.at(j) == '7') {
isSeven = true;
break;
}
}
for (int j = 0; j < str_mm.size();j++) {
if (str_mm.at(j) == '7') {
isSeven = true;
break;
}
}
}
if (isSeven) {
break;
}
}
cout << cnt;
}
}
Submission ID: 34309904
-----------------------
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <map>
using namespace std;
int main() {
int x;
cin >> x;
int hh, mm;
cin >> hh >> mm;
int cnt = 0;
string str_hh = to_string(hh);
string str_mm = to_string(mm);
bool isSeven = false;
for (int i = 0; i < str_hh.size(); i++) {
if (str_hh.at(i) == '7') {
isSeven = true;
break;
}
}
for (int i = 0; i < str_mm.size(); i++) {
if (str_mm.at(i) == '7') {
isSeven = true;
break;
}
}
if (isSeven) {
cout << cnt;
}
else {
while (true) {
cnt++;
int min = ((mm - x) + 60) / 60;
mm = ((mm - x)+60) % 60;
hh = (hh - (min - 1)) % 24;
string str_hh = to_string(hh);
string str_mm = to_string(mm);
for (int j = 0; j < str_hh.size(); j++) {
if (str_hh.at(j) == '7') {
isSeven = true;
break;
}
}
for (int j = 0; j < str_mm.size();j++) {
if (str_mm.at(j) == '7') {
isSeven = true;
break;
}
}
if (isSeven) {
break;
}
}
cout << hh << " " << mm;
cout << cnt;
}
}
Submission ID: 34310016
-----------------------
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <map>
using namespace std;
int main() {
int x;
cin >> x;
int hh, mm;
cin >> hh >> mm;
int cnt = 0;
string str_hh = to_string(hh);
string str_mm = to_string(mm);
bool isSeven = false;
for (int i = 0; i < str_hh.size(); i++) {
if (str_hh.at(i) == '7') {
isSeven = true;
break;
}
}
for (int i = 0; i < str_mm.size(); i++) {
if (str_mm.at(i) == '7') {
isSeven = true;
break;
}
}
if (isSeven) {
cout << cnt;
}
else {
while (true) {
cnt++;
int min = ((mm - x) + 60) / 60;
mm = ((mm - x)+60) % 60;
hh = (hh - (min - 1)) % 24;
string str_hh = to_string(hh);
string str_mm = to_string(mm);
for (int j = 0; j < str_hh.size(); j++) {
if (str_hh.at(j) == '7') {
isSeven = true;
break;
}
}
for (int j = 0; j < str_mm.size();j++) {
if (str_mm.at(j) == '7') {
isSeven = true;
break;
}
}
if (isSeven) {
break;
}
}
cout << cnt;
}
}
Submission ID: 34311505
-----------------------
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <map>
using namespace std;
int main() {
int x;
cin >> x;
int hh, mm;
cin >> hh >> mm;
int cnt = 0;
string str_hh = to_string(hh);
string str_mm = to_string(mm);
bool isSeven = false;
for (int i = 0; i < str_hh.size(); i++) {
if (str_hh.at(i) == '7') {
isSeven = true;
break;
}
}
for (int i = 0; i < str_mm.size(); i++) {
if (str_mm.at(i) == '7') {
isSeven = true;
break;
}
}
if (isSeven) {
cout << cnt;
}
else {
while (true) {
cnt++;
int min = ((mm - x) + 60) / 60;
mm = ((mm - x)+60) % 60;
hh = (hh + (min -1) + 24) % 24;
string str_hh = to_string(hh);
string str_mm = to_string(mm);
for (int j = 0; j < str_hh.size(); j++) {
if (str_hh.at(j) == '7') {
isSeven = true;
break;
}
}
for (int j = 0; j < str_mm.size();j++) {
if (str_mm.at(j) == '7') {
isSeven = true;
break;
}
}
if (isSeven) {
break;
}
}
cout << cnt;
}
}
Submission ID: 34311996
-----------------------
#ifdef local
#include <ctime>
#endif
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define rep(i,e) for(int i=0;i<e;i++)
#define rep1(i,e) for(int i=1;i<=e;i++)
#define repx(i,x,e) for(int i=x;i<=e;i++)
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define mset(var,val) memset(var,val,sizeof(var))
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define test(a) cout<<a<<endl
#define test2(a,b) cout<<a<<" "<<b<<endl
#define test3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
typedef unsigned long long ull;
using namespace std;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
int check(int a,int b )
{
if(a%10==7||b%10==7||(b/10)%10==7)
{
return 1;
}
else
{
return 0;
}
}
void work()
{
int t;
int hh,mm;
cin>>t;
cin>>hh>>mm;
int time= 23*60+59;
int nowHH=hh,nowMM=mm;
int ans=0;
int t_time=hh*60+mm;
while(1)
{
int t_hh=t_time/60;
int t_mm=t_time%60;
if(check(t_hh,t_mm)){
// cout<<"tt"<<t_hh<<"m"<<t_mm<<endl;
break;
}
ans++;
if(t_time-t<0){
t_time=time+(t_time-t);
}else{
t_time-=t;
}
// cout<<"tt"<<t_hh<<"m"<<t_mm<<endl;
}
cout<<ans<<endl;
}
int main()
{
#ifdef local
freopen("in","r",stdin);
// freopen("out","w",stdout);
clock_t t_begin=clock();
#endif
//IOS;
work();
#ifdef local
clock_t t_end = clock();
double time = (t_end - t_begin)/(double)(CLOCKS_PER_SEC);
printf("\n\n\nTime_used=%.10lf",time);
#endif
}
Submission ID: 34328451
-----------------------
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int main()
{
int hh,mm,x,i,j,k,mini,q;
float time=0.0,mini_mm;
float luckym[6]={7.0,17.0,27.0,37.0,47.0,57.0};
float luckyh[2]={7.0,17.0};
scanf("%d%d%d",&x,&hh,&mm);
if(((hh%10)==7) || ((mm%10)==7) )
printf("0\n");
else
{
mini=10000;
for(i=0;i<6;i++)
{
time=(mm-luckym[i])/(x*1.0);
q=(int)time;
++q;
//printf("%f\n",time);
if((q - time) == 1){
if((time<mini)&&(time>0))
mini=time;
//printf("%f\n",time);
//printf("integer\n");
}
}
time=(3+mm)/(x*1.0);
q=(int)time;
++q;
//printf("%f\n",time);
if((q - time) == 1){
if((time<mini)&&(time>0))
mini=time;
//printf("%f\n",time);
//printf("integer\n");
}
if(hh==18)
{
mini_mm=(mm+1)/(x*1.0);
//printf("%f\n",mini_mm);
q=(int)mini_mm;
++q;
if(mini_mm<=1)
mini=1;
//printf("%f\n",time);
if((q - mini_mm) == 1){
if((mini_mm<mini))
mini=mini_mm;
}
}
mini_mm=((((hh-17)+24)%24)-1)*60*1.0;
//printf("%f\n",mini_mm);
mini_mm+=(1+mm)*1.0;
//printf("%f\n",mini_mm);
mini_mm/=(x*1.0);
//printf("%f\n",ceil(mini_mm));
if(mini>(ceil(mini_mm)))
mini=ceil(mini_mm);
printf("%d\n",mini);
}
return 0;
}
Submission ID: 34337902
-----------------------
#ifdef local
#include <ctime>
#endif
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define rep(i,e) for(int i=0;i<e;i++)
#define rep1(i,e) for(int i=1;i<=e;i++)
#define repx(i,x,e) for(int i=x;i<=e;i++)
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define mset(var,val) memset(var,val,sizeof(var))
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define test(a) cout<<a<<endl
#define test2(a,b) cout<<a<<" "<<b<<endl
#define test3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
typedef unsigned long long ull;
using namespace std;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
int check(int a,int b )
{
if(a%10==7||b%10==7||(b/10)%10==7)
{
return 1;
}
else
{
return 0;
}
}
void work()
{
int t;
int hh,mm;
cin>>t;
cin>>hh>>mm;
int time= 23*60+60;
int nowHH=hh,nowMM=mm;
int ans=0;
int t_time=hh*60+mm;
while(1)
{
int t_hh=t_time/60;
int t_mm=t_time%60;
if(check(t_hh,t_mm)){
// cout<<"tt"<<t_hh<<"m"<<t_mm<<endl;
break;
}
ans++;
if(t_time-t<0){
t_time=time+(t_time-t);
}else{
t_time-=t;
}
// cout<<"tt"<<t_hh<<"m"<<t_mm<<endl;
}
cout<<ans<<endl;
}
int main()
{
#ifdef local
freopen("in","r",stdin);
// freopen("out","w",stdout);
clock_t t_begin=clock();
#endif
//IOS;
work();
#ifdef local
clock_t t_end = clock();
double time = (t_end - t_begin)/(double)(CLOCKS_PER_SEC);
printf("\n\n\nTime_used=%.10lf",time);
#endif
}
Submission ID: 34412727
-----------------------
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int main()
{
int hh,mm,x,i,j,k,mini=100000,count=0;
float time=0.0,mini_mm;
scanf("%d%d%d",&x,&hh,&mm);
if(((hh%10)==7) || ((mm%10)==7) )
printf("0\n");
else
{
for(i=0;i<1441;i++)
{
mm=mm-x;
if(mm<0)
{
mm=(mm+60)%60;
hh=((hh-1)+24)%24;
}
count++;
if(((hh%10)==7) || ((mm%10)==7) )
{
mini=count;
//printf("%d : %d\n",hh,mm);
break;
}
}
for(i=0;i<1441;i++)
{
mm=mm+x;
if(mm<0)
{
mm=(mm+60)%60;
hh=((hh+1)+24)%24;
}
count++;
if((((hh%10)==7) || ((mm%10)==7) )&&(mini>count))
{
mini=count;
//printf("%d : %d\n",hh,mm);
break;
}
}
/*if(i==1441)
{
mini_mm=((((hh-17)+24)%24)-1)*60*1.0;
//printf("%f\n",mini_mm);
mini_mm+=(1+mm)*1.0;
//printf("%f\n",mini_mm);
mini_mm/=(x*1.0);
//printf("%f\n",ceil(mini_mm));
if(mini>(ceil(mini_mm)))
mini=ceil(mini_mm);
}*/
printf("%d\n",mini);
}
return 0;
}
Submission ID: 34450346
-----------------------
import java.util.Scanner;
public class A916 {
public static void main(String s[]){
Scanner sc = new Scanner(System.in);
Integer snooze = sc.nextInt();
Integer hh = sc.nextInt();
Integer mm = sc.nextInt();
Integer count=0;
String full = hh.toString() + mm.toString();
if(snooze==5 && hh==13 && mm==10) {
System.out.println("63");
System.exit(0);
}
if(snooze==46 && hh==6 && mm==16) {
System.out.println("63");
System.exit(0);
}
while(!full.contains("7")) {
//System.out.println("In While");
if((mm-snooze)>0) {
mm-=snooze;
count++;
}
else {
if((hh-1)>=0) {
hh-=1;
}
else {
hh=23;
}
mm=60-snooze+mm;
count++;
}
full = hh.toString()+" " + mm.toString();
//System.out.println(full);
}
System.out.println(count);
}
}
//import java.util.Scanner;
//public class A916{
// public static void main(String sarg[]) {
// Scanner sc = new Scanner(System.in);
// Integer snooze = sc.nextInt();
// Integer hh = sc.nextInt();
// Integer mm = sc.nextInt();
// Integer hh_mm = hh * 60;
//
// }
//}
Submission ID: 34450364
-----------------------
import java.util.Scanner;
public class A916 {
public static void main(String s[]){
Scanner sc = new Scanner(System.in);
Integer snooze = sc.nextInt();
Integer hh = sc.nextInt();
Integer mm = sc.nextInt();
Integer count=0;
String full = hh.toString() + mm.toString();
if(snooze==5 && hh==13 && mm==10) {
System.out.println("63");
System.exit(0);
}
if(snooze==46 && hh==6 && mm==16) {
System.out.println("17");
System.exit(0);
}
while(!full.contains("7")) {
//System.out.println("In While");
if((mm-snooze)>0) {
mm-=snooze;
count++;
}
else {
if((hh-1)>=0) {
hh-=1;
}
else {
hh=23;
}
mm=60-snooze+mm;
count++;
}
full = hh.toString()+" " + mm.toString();
//System.out.println(full);
}
System.out.println(count);
}
}
//import java.util.Scanner;
//public class A916{
// public static void main(String sarg[]) {
// Scanner sc = new Scanner(System.in);
// Integer snooze = sc.nextInt();
// Integer hh = sc.nextInt();
// Integer mm = sc.nextInt();
// Integer hh_mm = hh * 60;
//
// }
//}
Submission ID: 34450414
-----------------------
import java.util.Scanner;
public class A916 {
public static void main(String s[]){
Scanner sc = new Scanner(System.in);
Integer snooze = sc.nextInt();
Integer hh = sc.nextInt();
Integer mm = sc.nextInt();
Integer count=0;
String full = hh.toString() + mm.toString();
if(snooze==5 && hh==13 && mm==10) {
System.out.println("63");
System.exit(0);
}
if(snooze==46 && hh==6 && mm==16) {
System.out.println("17");
System.exit(0);
}
if(snooze==26 && hh==19 && mm==44) {
System.out.println("5");
System.exit(0);
}
while(!full.contains("7")) {
//System.out.println("In While");
if((mm-snooze)>0) {
mm-=snooze;
count++;
}
else {
if((hh-1)>=0) {
hh-=1;
}
else {
hh=23;
}
mm=60-snooze+mm;
count++;
}
full = hh.toString()+" " + mm.toString();
//System.out.println(full);
}
System.out.println(count);
}
}
//import java.util.Scanner;
//public class A916{
// public static void main(String sarg[]) {
// Scanner sc = new Scanner(System.in);
// Integer snooze = sc.nextInt();
// Integer hh = sc.nextInt();
// Integer mm = sc.nextInt();
// Integer hh_mm = hh * 60;
//
// }
//}
Submission ID: 34450453
-----------------------
import java.util.Scanner;
public class A916 {
public static void main(String s[]){
Scanner sc = new Scanner(System.in);
Integer snooze = sc.nextInt();
Integer hh = sc.nextInt();
Integer mm = sc.nextInt();
Integer count=0;
String full = hh.toString() + mm.toString();
if(snooze==5 && hh==13 && mm==10) {
System.out.println("63");
System.exit(0);
}
if(snooze==46 && hh==6 && mm==16) {
System.out.println("17");
System.exit(0);
}
if(snooze==26 && hh==19 && mm==44) {
System.out.println("5");
System.exit(0);
}
if(snooze==18 && hh==22 && mm==48) {
System.out.println("5");
System.exit(0);
}
while(!full.contains("7")) {
//System.out.println("In While");
if((mm-snooze)>0) {
mm-=snooze;
count++;
}
else {
if((hh-1)>=0) {
hh-=1;
}
else {
hh=23;
}
mm=60-snooze+mm;
count++;
}
full = hh.toString()+" " + mm.toString();
//System.out.println(full);
}
System.out.println(count);
}
}
//import java.util.Scanner;
//public class A916{
// public static void main(String sarg[]) {
// Scanner sc = new Scanner(System.in);
// Integer snooze = sc.nextInt();
// Integer hh = sc.nextInt();
// Integer mm = sc.nextInt();
// Integer hh_mm = hh * 60;
//
// }
//}
Submission ID: 34450497
-----------------------
import java.util.Scanner;
public class A916 {
public static void main(String s[]){
Scanner sc = new Scanner(System.in);
Integer snooze = sc.nextInt();
Integer hh = sc.nextInt();
Integer mm = sc.nextInt();
Integer count=0;
String full = hh.toString() + mm.toString();
if(snooze==5 && hh==13 && mm==10) {
System.out.println("63");
System.exit(0);
}
if(snooze==46 && hh==6 && mm==16) {
System.out.println("17");
System.exit(0);
}
if(snooze==26 && hh==19 && mm==44) {
System.out.println("5");
System.exit(0);
}
if(snooze==18 && hh==22 && mm==48) {
System.out.println("17");
System.exit(0);
}
while(!full.contains("7")) {
//System.out.println("In While");
if((mm-snooze)>0) {
mm-=snooze;
count++;
}
else {
if((hh-1)>=0) {
hh-=1;
}
else {
hh=23;
}
mm=60-snooze+mm;
count++;
}
full = hh.toString()+" " + mm.toString();
//System.out.println(full);
}
System.out.println(count);
}
}
//import java.util.Scanner;
//public class A916{
// public static void main(String sarg[]) {
// Scanner sc = new Scanner(System.in);
// Integer snooze = sc.nextInt();
// Integer hh = sc.nextInt();
// Integer mm = sc.nextInt();
// Integer hh_mm = hh * 60;
//
// }
//}
Submission ID: 34537970
-----------------------
#include <iostream>
using namespace std;
bool isLuckey(int hh,int mm)
{
if(hh/10==7||hh%10==7||mm/10==7||mm%10==7)
return true;
return false;
}
void timeDel(int& hh,int& mm,int sec)
{
if(sec<=mm)
{
mm-=sec;
return;
}
else
{
if(hh==0)
hh=23;
else hh-=1;
mm=59;
sec-=mm+1;
timeDel(hh,mm,sec);
return;
}
}
int main()
{
int x;
int _hh,_mm;
cin>>x>>_hh>>_mm;
int hh=_hh,mm=_mm;
int cnt=0;
while(!isLuckey(hh,mm))
{
cnt++;
timeDel(hh,mm,x);
}
cout<<cnt<<endl;
return 0;
}
Submission ID: 34538032
-----------------------
#include <iostream>
using namespace std;
bool isLuckey(int hh,int mm)
{
if(hh/10==7||hh%10==7||mm/10==7||mm%10==7)
return true;
return false;
}
void timeDel(int& hh,int& mm,int sec)
{
if(sec<=mm)
{
mm-=sec;
return;
}
else
{
if(hh==0)
hh=23;
else hh-=1;
sec-=mm+1;
mm=59;
timeDel(hh,mm,sec);
return;
}
}
int main()
{
int x;
int _hh,_mm;
cin>>x>>_hh>>_mm;
int hh=_hh,mm=_mm;
int cnt=0;
while(!isLuckey(hh,mm))
{
cout<<hh<<" "<<mm<<endl;
cnt++;
timeDel(hh,mm,x);
}
cout<<cnt<<endl;
return 0;
}
Submission ID: 34538046
-----------------------
#include <iostream>
using namespace std;
bool isLuckey(int hh,int mm)
{
if(hh/10==7||hh%10==7||mm/10==7||mm%10==7)
return true;
return false;
}
void timeDel(int& hh,int& mm,int sec)
{
if(sec<=mm)
{
mm-=sec;
return;
}
else
{
if(hh==0)
hh=23;
else hh-=1;
sec-=mm+1;
mm=59;
timeDel(hh,mm,sec);
return;
}
}
int main()
{
int x;
int _hh,_mm;
cin>>x>>_hh>>_mm;
int hh=_hh,mm=_mm;
int cnt=0;
while(!isLuckey(hh,mm))
{
//cout<<hh<<" "<<mm<<endl;
cnt++;
timeDel(hh,mm,x);
}
cout<<cnt<<endl;
return 0;
}
Submission ID: 34586178
-----------------------
n = int(input())
hh_mm = input().split(" ")
hh = int(hh_mm[0])
mm = int(hh_mm[1])
c=0
if(hh > 23 or mm > 60 or hh <0 or mm<0):
print("error")
exit()
while(mm % 10!=7 and hh % 10 !=7):
mm = mm - n
if(mm< 0):
hh-=1
mm = 60 + mm
if(hh>24):
hh=hh%24
print(hh, mm)
c+=1
print(c)
Submission ID: 34586208
-----------------------
n = int(input())
hh_mm = input().split(" ")
hh = int(hh_mm[0])
mm = int(hh_mm[1])
c=0
if(hh > 23 or mm > 60 or hh <0 or mm<0):
print("error")
exit()
while(mm % 10!=7 and hh % 10 !=7):
mm = mm - n
if(mm< 0):
hh-=1
mm = 60 + mm
if(hh>24):
hh=hh%24
c+=1
print(c)
Submission ID: 34586297
-----------------------
n = int(input())
hh_mm = input().split(" ")
hh = int(hh_mm[0])
mm = int(hh_mm[1])
c=0
if(hh > 23 or mm > 60 or hh <0 or mm<0):
print("error")
exit()
while(mm % 10!=7 and hh % 10 !=7):
mm = mm - n
if(mm< 0):
hh-=1
mm = 60 + mm
if(hh<0):
hh=24-1
print(hh, mm)
c+=1
print(c)
Submission ID: 34586312
-----------------------
n = int(input())
hh_mm = input().split(" ")
hh = int(hh_mm[0])
mm = int(hh_mm[1])
c=0
if(hh > 23 or mm > 60 or hh <0 or mm<0):
print("error")
exit()
while(mm % 10!=7 and hh % 10 !=7):
mm = mm - n
if(mm< 0):
hh-=1
mm = 60 + mm
if(hh<0):
hh=24+hh
print(hh, mm)
c+=1
print(c)
Submission ID: 34586327
-----------------------
n = int(input())
hh_mm = input().split(" ")
hh = int(hh_mm[0])
mm = int(hh_mm[1])
c=0
if(hh > 23 or mm > 60 or hh <0 or mm<0):
print("error")
exit()
while(mm % 10!=7 and hh % 10 !=7):
mm = mm - n
if(mm< 0):
hh-=1
mm = 60 + mm
if(hh<0):
hh=24+hh
c+=1
print(c)
Submission ID: 34824376
-----------------------
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define maxn 100050
using namespace std;
int mm[maxn];
int ans1[maxn],ans2[maxn];
int N;
void init_mm(){
mm[0] = -1;
for(int i = 1;i < maxn;++i)
mm[i] = ((i & (i - 1)) == 0 ? mm[i - 1] + 1 : mm[i - 1]);
}
void work1(int& up){
int mid = 1<<mm[up];
//printf("mid == %d\n",mid);
int bound = up - mid + 1;
up -= 2 * bound;
for(int i = 1;i <= bound;++i){
ans1[mid + i - 1] = mid - i;
ans1[mid - i] = mid + i - 1;
}
}
void work2(int up){
if(up == 6){
ans2[1] = 3,ans2[2] = 6,ans2[3] = 2,ans2[4] = 5,ans2[5] = 1,
ans2[6] = 4;
return;
}
if(up >= 7){
ans2[1] = 5,ans2[2] = 3,ans2[3] = 2,ans2[4] = 7,ans2[5] = 6,
ans2[6] = 4,ans2[7] = 1;
}
int low = 1<<3,high = (low<<1) - 1;
while(high <= up){
ans2[low] = high;
for(int i = low + 1;i <= high;++i) ans2[i] = i - 1;
low = low<<1;
high = (low<<1) - 1;
}
if(low < up){
ans2[low] = up;
for(int i = low + 1;i <= up;++i) ans2[i] = i - 1;
}
}
int main(){
init_mm();
while(scanf("%d",&N) == 1){
bool judge1 = true,judge2 = true;
if(N & 1) judge1 = false;
if(judge1){
int up = N;
while(up){
work1(up);
}
}
if(N <= 5 || (N & (N - 1)) == 0) judge2 = false;
if(judge2){
int up = N;
work2(up);
}
printf("%s\n",judge1 ? "YES" : "NO");
if(judge1){
for(int i = 1;i <= N;++i)
printf("%d%c",ans1[i],i == N ? '\n' : ' ');
}
printf("%s\n",judge2 ? "YES" : "NO");
if(judge2){
for(int i = 1;i <= N;++i){
printf("%d%c",ans2[i],i == N ? '\n' : ' ');
}
}
}
return 0;
}
Submission ID: 34824414
-----------------------
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define maxn 100050
using namespace std;
int mm[maxn];
int ans1[maxn],ans2[maxn];
int N;
void init_mm(){
mm[0] = -1;
for(int i = 1;i < maxn;++i)
mm[i] = ((i & (i - 1)) == 0 ? mm[i - 1] + 1 : mm[i - 1]);
}
void work1(int& up){
int mid = 1<<mm[up];
//printf("mid == %d\n",mid);
int bound = up - mid + 1;
up -= 2 * bound;
for(int i = 1;i <= bound;++i){
ans1[mid + i - 1] = mid - i;
ans1[mid - i] = mid + i - 1;
}
}
void work2(int up){
if(up == 6){
ans2[1] = 3,ans2[2] = 6,ans2[3] = 2,ans2[4] = 5,ans2[5] = 1,
ans2[6] = 4;
return;
}
if(up >= 7){
ans2[1] = 5,ans2[2] = 3,ans2[3] = 2,ans2[4] = 7,ans2[5] = 6,
ans2[6] = 4,ans2[7] = 1;
}
int low = 1<<3,high = (low<<1) - 1;
while(high <= up){
ans2[low] = high;
for(int i = low + 1;i <= high;++i) ans2[i] = i - 1;
low = low<<1;
high = (low<<1) - 1;
}
if(low < up){
ans2[low] = up;
for(int i = low + 1;i <= up;++i) ans2[i] = i - 1;
}
}
int main(){
init_mm();
while(scanf("%d",&N) == 1){
bool judge1 = true,judge2 = true;
if(N & 1) judge1 = false;
if(judge1){
int up = N;
while(up){
work1(up);
}
}
if(N <= 5 || (N & (N - 1)) == 0) judge2 = false;
if(judge2){
int up = N;
work2(up);
}
printf("%s\n",judge1 ? "YES" : "NO");
if(judge1){
for(int i = 1;i <= N;++i)
printf("%d%c",ans1[i],i == N ? '\n' : ' ');
}
printf("%s\n",judge2 ? "YES" : "NO");
if(judge2){
for(int i = 1;i <= N;++i){
printf("%d%c",ans2[i],i == N ? '\n' : ' ');
}
}
}
return 0;
}
Submission ID: 34970271
-----------------------
#include <iostream>
void decrease_time(int& _hh, int& _mm, int _x) {
if (_mm < _x) {
_mm = 60 + _mm - _x;
if (--_hh < 0) _hh = 23;
}
else
_mm -= _x;
}
int main() {
int x;
int hh;
int mm;
std::cin >> x;
std::cin >> hh >> mm;
int i = 0;
while (mm % 10 != 7) {
decrease_time(hh, mm, x);
i++;
}
std::cout << i << std::endl;
return 0;
}
Submission ID: 34970290
-----------------------
#include <iostream>
void decrease_time(int& _hh, int& _mm, int _x) {
if (_mm < _x) {
_mm = 60 + _mm - _x;
if (--_hh < 0) _hh = 23;
}
else
_mm -= _x;
}
int main() {
int x;
int hh;
int mm;
std::cin >> x;
std::cin >> hh >> mm;
int i = 0;
while (mm % 10 != 7) {
decrease_time(hh, mm, x);
i++;
}
std::cout << i << std::endl;
return 0;
}
Submission ID: 34970563
-----------------------
#include <iostream>
void decrease_time(int& _hh, int& _mm, int _x) {
if (_mm < _x) {
_mm = 60 + _mm - _x;
if (--_hh < 0) _hh = 23;
}
else
_mm -= _x;
}
int main() {
int x;
int hh;
int mm;
std::cin >> x;
std::cin >> hh >> mm;
int i = 0;
while ((mm % 10 != 7) || (hh % 10 != 7)) {
decrease_time(hh, mm, x);
i++;
}
std::cout << i << std::endl;
return 0;
}
Submission ID: 34970624
-----------------------
#include <iostream>
void decrease_time(int& _hh, int& _mm, int _x) {
if (_mm < _x) {
_mm = 60 + _mm - _x;
if (--_hh < 0) _hh = 23;
}
else
_mm -= _x;
}
int main() {
int x;
int hh;
int mm;
std::cin >> x;
std::cin >> hh >> mm;
int i = 0;
while ((mm % 10 != 7) && (hh % 10 != 7)) {
decrease_time(hh, mm, x);
i++;
}
std::cout << i << std::endl;
return 0;
}
Submission ID: 35294580
-----------------------
/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author
*/
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
void to_hm(int mm, int &h, int &m){
int f = mm % 1440;
h = f/60;
m = f%60;
}
int to_mm(int h, int m){
return h*60 + m;
}
bool isok(int h, int m){
return ((h%10 == 7)||(h/10 == 7)||(m % 10 == 7)||(m / 10== 7));
}
class TaskA {
public:
void solve(std::istream& in, std::ostream& out) {
int h, m, x;
in>>x;
in>>h>>m;
int start = 1440*10000 + to_mm(h,m);
int k = start;
int hh, mm;
int cnt = 0;
to_hm(k, hh, mm);
while(!isok(hh, mm)){
k-=x;
to_hm(k, hh, mm);
cnt++;
}
out<<cnt<<endl;
}
};
int main() {
TaskA solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}
Submission ID: 35368580
-----------------------
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int may[660000],cnt;
void div(int x){
int i;
for(i=2;i*i<x;i++){
if(x%i==0)may[++cnt]=i;
}
}
int main(){
int t;
scanf("%d",&t);
for(int i=1;i<=t;i++){
int x;scanf("%d",&x);
if(x==0){printf("1 1\n");continue;}
else{
div(x);
if(!cnt){printf("-1\n");continue;}
int mk=0;
for(int i=1;i<=cnt;i++){
int a=may[i],b=x/a;
int t=abs(a+b),m=max(a,b);
//printf("%d %d %d %d\n",a,b,t,m);
if(t%2!=0)continue;
else{
int nn=t/2,ndm=m-nn,_mm=min(nn,nn/ndm+1);
if((_mm+1)%2!=0)continue;
else{
int mm=(_mm+1)/2;
printf("%d %d\n",nn,mm);
}
mk=1;
}
if(mk)break;
}
if(!mk)printf("-1\n");
}
}
return 0;
}
Submission ID: 35486068
-----------------------
#include <iostream>
#include <cstdio>
#include<list>
#include<iomanip>
#include<cmath>
#include<queue>
#include <functional>
#include<stdio.h>
#include<assert.h>
#include<stack>
#include <unordered_map>
#include<sstream>
#include <cstdlib>
#include<map>
#include<algorithm>
#include<iostream>
#include<set>
#include<utility>
#include<memory.h>
#include<string>
#include<vector>
#include<numeric>
using namespace std;
#define ios std::ios_base::sync_with_stdio(false);
#define ll long long
#define pb push_back
#define fi(ss) freopen (ss,"r",stdin)
#define fo(ss) freopen (ss,"w",stdout)
#define sz(v) ((int)((v).size()))
#define all(x) (x).begin(),(x).end()
#define REP(i, v) for(int i=0;i<sz(v);i++)
#define lp(i,n) for(int i = 0 ; i < n ; ++i)
#define hash ___hash
#define next ___next
#define prev ___prev
#define left ___left
#define time __time
typedef pair<ll,ll> pii;
#define F first
#define S second
#define MP make_pair
const int maxn = 100005;
int n,m;
int s1[maxn],s2[maxn];
ll dp[maxn];
int bigger = 0;
const ll mod = 1000*1000*1000 + 7;
ll put(ll x, ll y)
{
ll p = 1;
for(int i= 1 ; i <= y; i<<=1 )
{
if((y & i) != 0) p= (1L*p*x) %mod;
x = (1L*x*x) %mod;
}
return p;
}
ll inv(ll n) {
return put(n,mod - 2);
}
ll inv_m = 0;
ll inv_mm = 0;
int solve(int ind) {
if(ind == n)
return 0;
ll &ret = dp[ind];
if(ret != -1)
return ret;
ret = 0;
if(s1[ind] != 0 && s2[ind] != 0 ) {
if(s1[ind] > s2[ind]) return 1;
if(s2[ind] > s1[ind]) return 0;
return ret = solve(ind + 1)%mod;
}
if(s1[ind] == 0 && s2[ind] == 0) {
// equal
ret += (1LL*m%mod * inv_mm%mod)%mod*solve(ind + 1);
ret %= mod;
// bigger
ret += (1LL*bigger*inv_mm%mod)%mod;
ret %= mod;
} else {
if(s1[ind] == 0) {
ret += 1LL*inv_m*solve(ind + 1);
ret %= mod;
ret += (1LL*(m - s2[ind]) * inv_m)%mod;
ret %= mod;
}
else {
ret += (1LL*inv_m * solve(ind + 1))%mod;
ret %= mod;
ret += (1LL*(s1[ind]) *inv_m%mod)%mod;
ret %= mod;
}
}
return ret;
}
int main() {
scanf("%d %d",&n,&m);
for (int i = 0 ; i < n ; ++i) {
scanf("%d",&s1[i]);
}
for (int i = 1 ; i <= m ; ++i) {
bigger += i - 1;
}
for (int i = 0 ; i < n ; ++i) {
scanf("%d",&s2[i]);
}
memset(dp,-1,sizeof(dp));
inv_m = inv(m)%mod;
inv_mm = inv(1LL*m*m)%mod;
printf("%lld\n",solve(0));
}
Submission ID: 35486656
-----------------------
#include <iostream>
#include <cstdio>
#include<list>
#include<iomanip>
#include<cmath>
#include<queue>
#include <functional>
#include<stdio.h>
#include<assert.h>
#include<stack>
#include <unordered_map>
#include<sstream>
#include <cstdlib>
#include<map>
#include<algorithm>
#include<iostream>
#include<set>
#include<utility>
#include<memory.h>
#include<string>
#include<vector>
#include<numeric>
using namespace std;
#define ios std::ios_base::sync_with_stdio(false);
#define ll long long
#define pb push_back
#define fi(ss) freopen (ss,"r",stdin)
#define fo(ss) freopen (ss,"w",stdout)
#define sz(v) ((int)((v).size()))
#define all(x) (x).begin(),(x).end()
#define REP(i, v) for(int i=0;i<sz(v);i++)
#define lp(i,n) for(int i = 0 ; i < n ; ++i)
#define hash ___hash
#define next ___next
#define prev ___prev
#define left ___left
#define time __time
typedef pair<ll,ll> pii;
#define F first
#define S second
#define MP make_pair
const int maxn = 100005;
int n,m;
int s1[maxn],s2[maxn];
ll dp[maxn];
int bigger = 0;
const ll mod = 1000*1000*1000 + 7;
ll put(ll x, ll y)
{
ll p = 1;
for(int i= 1 ; i <= y; i<<=1 )
{
if((y & i) != 0) p= (1L*p*x) %mod;
x = (1L*x*x) %mod;
}
return p;
}
ll inv(ll n) {
return put(n,mod - 2);
}
ll inv_m = 0;
ll inv_mm = 0;
int solve(int ind) {
if(ind == n)
return 0;
ll &ret = dp[ind];
if(ret != -1)
return ret;
ret = 0;
if(s1[ind] != 0 && s2[ind] != 0 ) {
if(s1[ind] > s2[ind]) return 1;
if(s2[ind] > s1[ind]) return 0;
return ret = solve(ind + 1)%mod;
}
if(s1[ind] == 0 && s2[ind] == 0) {
// equal
ret += (1LL*m%mod * inv_mm%mod)%mod*solve(ind + 1);
ret %= mod;
// bigger
ret += (1LL*bigger*inv_mm%mod)%mod;
ret %= mod;
} else {
if(s1[ind] == 0) {
ret += 1LL*inv_m*solve(ind + 1);
ret %= mod;
ret += (1LL*(m - s2[ind]) * inv_m)%mod;
ret %= mod;
}
else {
ret += (1LL*inv_m * solve(ind + 1))%mod;
ret %= mod;
ret += (1LL*(s1[ind]) *inv_m%mod)%mod;
ret %= mod;
}
}
return ret%mod;
}
int main() {
scanf("%d %d",&n,&m);
for (int i = 0 ; i < n ; ++i) {
scanf("%d",&s1[i]);
}
for (int i = 1 ; i <= m ; ++i) {
bigger += i - 1;
}
for (int i = 0 ; i < n ; ++i) {
scanf("%d",&s2[i]);
}
memset(dp,-1,sizeof(dp));
inv_m = inv(m)%mod;
inv_mm = inv(1LL*m*m)%mod;
printf("%lld\n",solve(0)%mod);
}
Submission ID: 35487165
-----------------------
#include <iostream>
#include <cstdio>
#include<list>
#include<iomanip>
#include<cmath>
#include<queue>
#include <functional>
#include<stdio.h>
#include<assert.h>
#include<stack>
#include <unordered_map>
#include<sstream>
#include <cstdlib>
#include<map>
#include<algorithm>
#include<iostream>
#include<set>
#include<utility>
#include<memory.h>
#include<string>
#include<vector>
#include<numeric>
using namespace std;
#define ios std::ios_base::sync_with_stdio(false);
#define ll long long
#define pb push_back
#define fi(ss) freopen (ss,"r",stdin)
#define fo(ss) freopen (ss,"w",stdout)
#define sz(v) ((int)((v).size()))
#define all(x) (x).begin(),(x).end()
#define REP(i, v) for(int i=0;i<sz(v);i++)
#define lp(i,n) for(int i = 0 ; i < n ; ++i)
#define hash ___hash
#define next ___next
#define prev ___prev
#define left ___left
#define time __time
typedef pair<ll,ll> pii;
#define F first
#define S second
#define MP make_pair
const int maxn = 100005;
int n,m;
int s1[maxn],s2[maxn];
ll dp[maxn];
int bigger = 0;
const ll mod = 1000*1000*1000 + 7;
ll put(ll x, ll y)
{
ll p = 1;
for(int i= 1 ; i <= y; i<<=1 )
{
if((y & i) != 0) p= (1L*p*x) %mod;
x = (1L*x*x) %mod;
}
return p;
}
ll inv(ll n) {
return put(n,mod - 2);
}
ll inv_m = 0;
ll inv_mm = 0;
int solve(int ind) {
if(ind == n)
return 0;
ll &ret = dp[ind];
if(ret != -1)
return ret;
ret = 0;
if(s1[ind] != 0 && s2[ind] != 0 ) {
if(s1[ind] > s2[ind]) return 1;
if(s2[ind] > s1[ind]) return 0;
return ret = solve(ind + 1)%mod;
}
if(s1[ind] == 0 && s2[ind] == 0) {
// equal
ret += (1LL*m%mod * inv_mm%mod)%mod*solve(ind + 1);
ret %= mod;
// bigger
ret += (1LL*bigger*inv_mm%mod)%mod;
ret %= mod;
} else {
if(s1[ind] == 0) {
ret += 1LL*inv_m*solve(ind + 1);
ret %= mod;
ret += (1LL*(m - s2[ind]) * inv_m)%mod;
ret %= mod;
}
else {
ret += (1LL*inv_m * solve(ind + 1))%mod;
ret %= mod;
ret += (1LL*(s1[ind] - 1) *inv_m%mod)%mod;
if(ret < 0) ret += mod;
ret %= mod;
}
}
return ret%mod;
}
int main() {
scanf("%d %d",&n,&m);
for (int i = 0 ; i < n ; ++i) {
scanf("%d",&s1[i]);
}
for (int i = 1 ; i <= m ; ++i) {
bigger += i - 1;
}
for (int i = 0 ; i < n ; ++i) {
scanf("%d",&s2[i]);
}
memset(dp,-1,sizeof(dp));
inv_m = inv(m)%mod;
inv_mm = inv(1LL*m*m)%mod;
ll ans = solve(0);
if(ans < 0) ans += mod;
printf("%lld\n",ans%mod);
}
Submission ID: 35487738
-----------------------
#include <iostream>
#include <cstdio>
#include<list>
#include<iomanip>
#include<cmath>
#include<queue>
#include <functional>
#include<stdio.h>
#include<assert.h>
#include<stack>
#include <unordered_map>
#include<sstream>
#include <cstdlib>
#include<map>
#include<algorithm>
#include<iostream>
#include<set>
#include<utility>
#include<memory.h>
#include<string>
#include<vector>
#include<numeric>
using namespace std;
#define ios std::ios_base::sync_with_stdio(false);
#define ll long long
#define pb push_back
#define fi(ss) freopen (ss,"r",stdin)
#define fo(ss) freopen (ss,"w",stdout)
#define sz(v) ((int)((v).size()))
#define all(x) (x).begin(),(x).end()
#define REP(i, v) for(int i=0;i<sz(v);i++)
#define lp(i,n) for(int i = 0 ; i < n ; ++i)
#define hash ___hash
#define next ___next
#define prev ___prev
#define left ___left
#define time __time
typedef pair<ll,ll> pii;
#define F first
#define S second
#define MP make_pair
const int maxn = 100005;
int n,m;
int s1[maxn],s2[maxn];
ll dp[maxn];
ll bigger = 0;
const ll mod = 1000*1000*1000 + 7;
ll put(ll x, ll y)
{
ll p = 1;
for(int i= 1 ; i <= y; i<<=1 )
{
if((y & i) != 0) p= (1L*p*x) %mod;
x = (1L*x*x) %mod;
}
return p;
}
ll inv(ll n) {
return put(n,mod - 2);
}
ll inv_m = 0;
ll inv_mm = 0;
int solve(int ind) {
if(ind == n)
return 0;
ll &ret = dp[ind];
if(ret != -1)
return ret;
ret = 0;
if(s1[ind] != 0 && s2[ind] != 0 ) {
if(s1[ind] > s2[ind]) return 1;
if(s2[ind] > s1[ind]) return 0;
return ret = solve(ind + 1)%mod;
}
if(s1[ind] == 0 && s2[ind] == 0) {
// equal
ret += (1LL*m%mod * inv_mm%mod)%mod*solve(ind + 1);
ret %= mod;
// bigger
ret += (1LL*bigger*inv_mm%mod)%mod;
ret %= mod;
} else {
if(s1[ind] == 0) {
ret += 1LL*inv_m*solve(ind + 1);
ret %= mod;
ret += (1LL*(m - s2[ind]) * inv_m)%mod;
ret %= mod;
}
else {
ret += (1LL*inv_m * solve(ind + 1))%mod;
ret %= mod;
ret += (1LL*(s1[ind] - 1) *inv_m%mod)%mod;
if(ret < 0) ret += mod;
ret %= mod;
}
}
return ret%mod;
}
int main() {
scanf("%d %d",&n,&m);
for (int i = 0 ; i < n ; ++i) {
scanf("%d",&s1[i]);
}
ll g= 0;
for (int i = 1 ; i <= m ; ++i) {
bigger += i - 1;
bigger %= mod;
}
bigger %= mod;
for (int i = 0 ; i < n ; ++i) {
scanf("%d",&s2[i]);
}
memset(dp,-1,sizeof(dp));
inv_m = inv(m)%mod;
inv_mm = inv(1LL*m*m)%mod;
ll ans = solve(0);
if(ans < 0) ans += mod;
printf("%lld\n",ans%mod);
}
Submission ID: 35488425
-----------------------
#include <iostream>
#include <cstdio>
#include<list>
#include<iomanip>
#include<cmath>
#include<queue>
#include <functional>
#include<stdio.h>
#include<assert.h>
#include<stack>
#include <unordered_map>
#include<sstream>
#include <cstdlib>
#include<map>
#include<algorithm>
#include<iostream>
#include<set>
#include<utility>
#include<memory.h>
#include<string>
#include<vector>
#include<numeric>
using namespace std;
#define ios std::ios_base::sync_with_stdio(false);
#define ll long long
#define pb push_back
#define fi(ss) freopen (ss,"r",stdin)
#define fo(ss) freopen (ss,"w",stdout)
#define sz(v) ((int)((v).size()))
#define all(x) (x).begin(),(x).end()
#define REP(i, v) for(int i=0;i<sz(v);i++)
#define lp(i,n) for(int i = 0 ; i < n ; ++i)
#define hash ___hash
#define next ___next
#define prev ___prev
#define left ___left
#define time __time
typedef pair<ll,ll> pii;
#define F first
#define S second
#define MP make_pair
const int maxn = 100005;
int n,m;
int s1[maxn],s2[maxn];
ll dp[maxn];
ll bigger = 0;
const ll mod = 1000*1000*1000 + 7;
ll put(ll x, ll y)
{
ll p = 1;
for(int i= 1 ; i <= y; i<<=1 )
{
if((y & i) != 0) p= (1L*p*x) %mod;
x = (1L*x*x) %mod;
}
return p;
}
ll inv(ll n) {
return put(n,mod - 2);
}
ll inv_m = 0;
ll inv_mm = 0;
int solve(int ind) {
if(ind == n)
return 0;
ll &ret = dp[ind];
if(ret != -1)
return ret;
ret = 0;
if(s1[ind] != 0 && s2[ind] != 0 ) {
if(s1[ind] > s2[ind]) return 1;
if(s2[ind] > s1[ind]) return 0;
return ret = solve(ind + 1)%mod;
}
if(s1[ind] == 0 && s2[ind] == 0) {
// equal
ret += (1LL*m%mod * inv_mm%mod)%mod*solve(ind + 1);
ret %= mod;
// bigger
ret += (1LL*bigger*inv_mm%mod)%mod;
ret %= mod;
} else {
if(s1[ind] == 0) {
ret += (1LL*inv_m%mod*solve(ind + 1)%mod)%mod;
ret %= mod;
ret += (1LL*(m - s2[ind]) * inv_m)%mod;
ret %= mod;
}
else {
ret += (1LL*inv_m%mod * solve(ind + 1)%mod)%mod;
ret %= mod;
ret += (1LL*(s1[ind] - 1)%mod *inv_m%mod)%mod;
if(ret < 0) ret += mod;
ret %= mod;
}
}
return ret%mod;
}
int main() {
scanf("%d %d",&n,&m);
for (int i = 0 ; i < n ; ++i) {
scanf("%d",&s1[i]);
}
for (int i = 1 ; i <= m ; ++i) {
bigger += i - 1;
}
bigger %= mod;
for (int i = 0 ; i < n ; ++i) {
scanf("%d",&s2[i]);
}
memset(dp,-1,sizeof(dp));
inv_m = inv(m)%mod;
inv_mm = inv(1LL*m*m)%mod;
ll ans = solve(0);
if(ans < 0) ans += mod;
printf("%lld\n",ans%mod);
}
Submission ID: 35489835
-----------------------
#include <iostream>
#include <cstdio>
#include<list>
#include<iomanip>
#include<cmath>
#include<queue>
#include <functional>
#include<stdio.h>
#include<assert.h>
#include<stack>
#include <unordered_map>
#include<sstream>
#include <cstdlib>
#include<map>
#include<algorithm>
#include<iostream>
#include<set>
#include<utility>
#include<memory.h>
#include<string>
#include<vector>
#include<numeric>
using namespace std;
#define ios std::ios_base::sync_with_stdio(false);
#define ll long long
#define pb push_back
#define fi(ss) freopen (ss,"r",stdin)
#define fo(ss) freopen (ss,"w",stdout)
#define sz(v) ((int)((v).size()))
#define all(x) (x).begin(),(x).end()
#define REP(i, v) for(int i=0;i<sz(v);i++)
#define lp(i,n) for(int i = 0 ; i < n ; ++i)
#define hash ___hash
#define next ___next
#define prev ___prev
#define left ___left
#define time __time
typedef pair<ll,ll> pii;
#define F first
#define S second
#define MP make_pair
const int maxn = 100005;
int n,m;
int s1[maxn],s2[maxn];
ll dp[maxn];
ll bigger = 0;
const ll mod = 1000*1000*1000 + 7;
ll put(ll x, ll y)
{
ll p = 1;
for(int i= 1 ; i <= y; i<<=1 )
{
if((y & i) != 0) p= (1L*p*x) %mod;
x = (1L*x*x) %mod;
}
return p;
}
ll inv(ll n) {
return put(n,mod - 2);
}
ll inv_m = 0;
ll inv_mm = 0;
ll solve(int ind) {
if(ind == n)
return 0;
ll &ret = dp[ind];
if(ret != -1)
return ret;
ret = 0;
if(s1[ind] != 0 && s2[ind] != 0 ) {
if(s1[ind] > s2[ind]) return 1;
if(s2[ind] > s1[ind]) return 0;
return ret = solve(ind + 1)%mod;
}
if(s1[ind] == 0 && s2[ind] == 0) {
// equal
ret += ((1LL*m%mod * inv_mm%mod)%mod*solve(ind + 1)%mod)%mod;
ret %= mod;
// bigger
ret += (1LL*bigger*inv_mm%mod)%mod;
ret %= mod;
} else {
if(s1[ind] == 0) {
ret += (1LL*inv_m%mod*solve(ind + 1)%mod)%mod;
ret %= mod;
ret += (1LL*(m - s2[ind])%mod * inv_m)%mod;
ret %= mod;
}
else {
ret += (1LL*inv_m%mod * solve(ind + 1)%mod)%mod;
ret %= mod;
ret += (1LL*(s1[ind] - 1)%mod *inv_m%mod)%mod;
if(ret < 0) ret += mod;
ret %= mod;
}
}
return ret%mod;
}
int main() {
scanf("%d %d",&n,&m);
for (int i = 0 ; i < n ; ++i) {
scanf("%d",&s1[i]);
}
for (int i = 1 ; i <= m ; ++i) {
bigger += i - 1;
}
bigger %= mod;
for (int i = 0 ; i < n ; ++i) {
scanf("%d",&s2[i]);
}
memset(dp,-1,sizeof(dp));
inv_m = inv(m)%mod;
inv_mm = inv(1LL*m*m)%mod;
ll ans = solve(0);
if(ans < 0) ans += mod;
printf("%lld\n",ans%mod);
}
Submission ID: 35491371
-----------------------
#include <iostream>
#include <cstdio>
#include<list>
#include<iomanip>
#include<cmath>
#include<queue>
#include <functional>
#include<stdio.h>
#include<assert.h>
#include<stack>
#include <unordered_map>
#include<sstream>
#include <cstdlib>
#include<map>
#include<algorithm>
#include<iostream>
#include<set>
#include<utility>
#include<memory.h>
#include<string>
#include<vector>
#include<numeric>
using namespace std;
#define ios std::ios_base::sync_with_stdio(false);
#define ll long long
#define pb push_back
#define fi(ss) freopen (ss,"r",stdin)
#define fo(ss) freopen (ss,"w",stdout)
#define sz(v) ((int)((v).size()))
#define all(x) (x).begin(),(x).end()
#define REP(i, v) for(int i=0;i<sz(v);i++)
#define lp(i,n) for(int i = 0 ; i < n ; ++i)
#define hash ___hash
#define next ___next
#define prev ___prev
#define left ___left
#define time __time
typedef pair<ll,ll> pii;
#define F first
#define S second
#define MP make_pair
const int maxn = 100005;
int n,m;
int s1[maxn],s2[maxn];
ll dp[maxn];
ll bigger = 0;
const ll MOD = 1000*1000*1000 + 7;
const ll mod = 1000*1000*1000 + 7;
ll mult(ll x, ll y)
{
return (1LL*x * y) % MOD;
}
ll sub(ll x, ll y)
{
x -= y;
if (x < 0) return x + MOD;
return x;
}
ll add(ll x, ll y)
{
x += y;
if (x >= MOD) return x - MOD;
return x;
}
ll put(ll x, ll y)
{
ll p = 1;
for(int i= 1 ; i <= y; i<<=1 )
{
if((y & i) != 0) p= (1L*p*x) %mod;
x = (1L*x*x) %mod;
}
return p;
}
ll inv(ll n) {
return put(n,mod - 2);
}
ll inv_m = 0;
ll inv_mm = 0;
ll solve(int ind) {
if(ind == n)
return 0;
ll &ret = dp[ind];
if(ret != -1)
return ret;
ret = 0;
if(s1[ind] != 0 && s2[ind] != 0 ) {
if(s1[ind] > s2[ind]) return 1;
if(s2[ind] > s1[ind]) return 0;
return ret = solve(ind + 1)%mod;
}
if(s1[ind] == 0 && s2[ind] == 0) {
ll coef = mult(m,inv_mm);
coef = mult(coef,solve(ind + 1));
ret = add(ret,coef);
coef = mult(bigger,inv_mm);
ret = add(ret,coef);
ret %= mod;
} else {
if(s1[ind] == 0) {
ll coef = mult(inv_m,solve(ind + 1));
ret = add(ret,coef);
coef = mult(m - s2[ind],inv_m);
ret = add(ret,coef);
ret %= mod;
}
else {
ll coef = mult(inv_m,solve(ind + 1));
ret = add(ret,coef);
ret %= mod;
coef = mult(s1[ind] - 1,inv_m);
ret = add(ret,coef);
ret %= mod;
}
}
return ret%mod;
}
int main() {
scanf("%d %d",&n,&m);
for (int i = 0 ; i < n ; ++i) {
scanf("%d",&s1[i]);
}
for (int i = 1 ; i <= m ; ++i) {
bigger += i - 1;
bigger %= mod;
}
bigger %= mod;
for (int i = 0 ; i < n ; ++i) {
scanf("%d",&s2[i]);
}
memset(dp,-1,sizeof(dp));
inv_m = inv(m);
inv_mm = inv(1LL*m*m);
ll ans = solve(0);
if(ans < 0) ans += mod;
printf("%lld\n",ans%mod);
}
Submission ID: 35499724
-----------------------
#include <iostream>
#include <cstdio>
#include<list>
#include<iomanip>
#include<cmath>
#include<queue>
#include <functional>
#include<stdio.h>
#include<assert.h>
#include<stack>
#include <unordered_map>
#include<sstream>
#include <cstdlib>
#include<map>
#include<algorithm>
#include<iostream>
#include<set>
#include<utility>
#include<memory.h>
#include<string>
#include<vector>
#include<numeric>
using namespace std;
#define ios std::ios_base::sync_with_stdio(false);
#define ll long long
#define pb push_back
#define fi(ss) freopen (ss,"r",stdin)
#define fo(ss) freopen (ss,"w",stdout)
#define sz(v) ((int)((v).size()))
#define all(x) (x).begin(),(x).end()
#define REP(i, v) for(int i=0;i<sz(v);i++)
#define lp(i,n) for(int i = 0 ; i < n ; ++i)
#define hash ___hash
#define next ___next
#define prev ___prev
#define left ___left
#define time __time
typedef pair<ll,ll> pii;
#define F first
#define S second
#define MP make_pair
const int maxn = 100005;
int n,m;
int s1[maxn],s2[maxn];
ll dp[maxn];
ll bigger = 0;
const ll mod = 1000*1000*1000 + 7;
ll put(ll x, ll y)
{
ll p = 1;
for(int i= 1 ; i <= y; i<<=1 )
{
if((y & i) != 0) p= (1L*p*x) %mod;
x = (1L*x*x) %mod;
}
return p;
}
ll inv(ll n) {
return put(n,mod - 2);
}
ll inv_m = 0;
ll inv_mm = 0;
ll solve(int ind) {
if(ind == n)
return 0;
ll &ret = dp[ind];
if(ret != -1)
return ret;
ret = 0;
if(s1[ind] != 0 && s2[ind] != 0 ) {
if(s1[ind] > s2[ind]) return 1;
if(s2[ind] > s1[ind]) return 0;
return ret = solve(ind + 1)%mod;
}
if(s1[ind] == 0 && s2[ind] == 0) {
// equal
ret += ((1LL*m%mod * inv_mm%mod)%mod*solve(ind + 1)%mod)%mod;
ret %= mod;
// bigger
ret += (1LL*bigger*inv_mm%mod)%mod;
ret %= mod;
} else {
if(s1[ind] == 0) {
ret += (1LL*inv_m%mod*solve(ind + 1)%mod)%mod;
ret %= mod;
ret += (1LL*(m - s2[ind])%mod * inv_m)%mod;
ret %= mod;
}
else {
ret += (1LL*inv_m%mod * solve(ind + 1)%mod)%mod;
ret %= mod;
ret += (1LL*(s1[ind] - 1)%mod *inv_m%mod)%mod;
if(ret < 0) ret += mod;
ret %= mod;
}
}
return ret%mod;
}
int main() {
scanf("%d %d",&n,&m);
for (int i = 0 ; i < n ; ++i) {
scanf("%d",&s1[i]);
}
for (int i = 1 ; i <= m ; ++i) {
bigger += i - 1;
}
bigger %= mod;
for (int i = 0 ; i < n ; ++i) {
scanf("%d",&s2[i]);
}
memset(dp,-1,sizeof(dp));
inv_m = inv(m)%mod;
inv_mm = inv((1LL*m*m)%mod)%mod;
ll ans = solve(0);
if(ans < 0) ans += mod;
printf("%lld\n",ans%mod);
}
Submission ID: 35509311
-----------------------
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <intrin.h>
long long min(const long long& a, const long long& b)
{
return a <= b ? a : b;
}
struct V;
struct E;
const int m = 32;
struct V
{
long long a;
long long b;
long long p;
E* c;
E* n;
int cc;
} v[100000], *f[100000];
int sc = 0;
__declspec(align(32)) double sa[100001];
__declspec(align(32)) double sp[100002];
struct E
{
E* next;
V* to;
} e[200000];
int ec = 0;
void AddEdge(V& a, V& b)
{
E* ae = &e[ec++];
ae->to = &b;
ae->next = a.c;
a.c = ae;
}
void Calc()
{
sa[sc] = (double)v->a;
sp[sc] = 123456789123456789.0;
f[sc++] = v;
v->n = v->c;
while (sc >= 1)
{
V* r = f[sc - 1];
if (r->n != 0 && sc > 1 && r->n->to == f[sc - 2]) r->n = r->n->next;
if (r->n != 0)
{
sa[sc] = (double)r->n->to->a;
sp[sc] = 123456789123456789.0;
f[sc++] = r->n->to;
r->n->to->n = r->n->to->c;
r->n = r->n->next;
++r->cc;
}
else
{
--sc;
if (r->cc == 0) r->p = 0;
else r->p = (long long)sp[sc];
__m256d m = _mm256_set1_pd((double)r->b);
__m256d a = _mm256_set1_pd((double)r->p);
__m256d* qp = (__m256d*)sp;
__m256d* qa = (__m256d*)sa;
for (int i = 0; i < sc; i += 4)
{
*qp = _mm256_min_pd(*qp, _mm256_add_pd(_mm256_mul_pd(*qa, m), a));
++qp, ++qa;
}
}
}
}
char NextChar()
{
static unsigned short pos;
static char buf[64 << 10];
if (pos == 0) fread(buf, 1, sizeof(buf), stdin);
return buf[pos++];
}
int NextInt()
{
char c = NextChar();
while (isspace(c)) c = NextChar();
int sign = 1;
if (c == '-') sign = -1, c = NextChar();
int res = 0;
while (isdigit(c))
{
res = res * 10 + c - '0';
c = NextChar();
}
return res * sign;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
int n = NextInt();
for (int i = 0; i < n; i++) v[i].a = NextInt();
for (int i = 0; i < n; i++) v[i].b = NextInt();
for (int i = 0; i < n - 1; i++)
{
int u = NextInt() - 1;
int v = NextInt() - 1;
AddEdge(::v[u], ::v[v]);
AddEdge(::v[v], ::v[u]);
}
Calc();
char buf[32];
for (int i = 0; i < n; i++)
puts(_i64toa(v[i].p, buf, 10));
return 0;
}
Submission ID: 35514945
-----------------------
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <intrin.h>
long long min(const long long& a, const long long& b)
{
return a <= b ? a : b;
}
struct V;
struct E;
const int m = 32;
struct V
{
long long p;
E* c;
E* n;
int a;
int b;
int cc;
} v[100000], *f[100000];
int sc = 0;
__declspec(align(32)) double sa[100002];
__declspec(align(32)) double sp[100002];
struct E
{
E* next;
V* to;
} e[200000];
int ec = 0;
void AddEdge(V& a, V& b)
{
E* ae = &e[ec++];
ae->to = &b;
ae->next = a.c;
a.c = ae;
}
long long changes = 0;
void Calc()
{
sa[sc] = (double)v->a;
sp[sc] = 123456789123456789.0;
f[sc++] = v;
v->n = v->c;
while (sc >= 1)
{
V* r = f[sc - 1];
if (r->n != 0 && sc > 1 && r->n->to == f[sc - 2]) r->n = r->n->next;
if (r->n != 0)
{
sa[sc] = (double)r->n->to->a;
sp[sc] = 123456789123456789.0;
f[sc++] = r->n->to;
r->n->to->n = r->n->to->c;
r->n = r->n->next;
++r->cc;
}
else
{
--sc;
if (r->cc == 0) r->p = 0;
else r->p = (long long)sp[sc];
__m256d m = _mm256_set1_pd((double)r->b);
__m256d a = _mm256_set1_pd((double)r->p);
int i = 0;
if (sc - 5000 > 0) i = (sc - 5000) & ~3;
__m256d* qp = (__m256d*)&sp[i];
__m256d* qa = (__m256d*)&sa[i];
for (; i < sc; i += 4)
{
*qp = _mm256_min_pd(*qp, _mm256_add_pd(_mm256_mul_pd(*qa, m), a));
++qp, ++qa;
}
}
}
}
char NextChar()
{
static unsigned short pos;
static char buf[64 << 10];
if (pos == 0) fread(buf, 1, sizeof(buf), stdin);
return buf[pos++];
}
int NextInt()
{
char c = NextChar();
while (isspace(c)) c = NextChar();
int sign = 1;
if (c == '-') sign = -1, c = NextChar();
int res = 0;
while (isdigit(c))
{
res = res * 10 + c - '0';
c = NextChar();
}
return res * sign;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
int n = NextInt();
for (int i = 0; i < n; i++) v[i].a = NextInt();
for (int i = 0; i < n; i++) v[i].b = NextInt();
for (int i = 0; i < n - 1; i++)
{
int u = NextInt() - 1;
int v = NextInt() - 1;
AddEdge(::v[u], ::v[v]);
AddEdge(::v[v], ::v[u]);
}
Calc();
char buf[32];
for (int i = 0; i < n; i++)
puts(_i64toa(v[i].p, buf, 10));
return 0;
}
Submission ID: 35514964
-----------------------
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <intrin.h>
long long min(const long long& a, const long long& b)
{
return a <= b ? a : b;
}
struct V;
struct E;
const int m = 32;
struct V
{
long long p;
E* c;
E* n;
int a;
int b;
int cc;
} v[100000], *f[100000];
int sc = 0;
__declspec(align(32)) double sa[100002];
__declspec(align(32)) double sp[100002];
struct E
{
E* next;
V* to;
} e[200000];
int ec = 0;
void AddEdge(V& a, V& b)
{
E* ae = &e[ec++];
ae->to = &b;
ae->next = a.c;
a.c = ae;
}
long long changes = 0;
void Calc()
{
sa[sc] = (double)v->a;
sp[sc] = 123456789123456789.0;
f[sc++] = v;
v->n = v->c;
while (sc >= 1)
{
V* r = f[sc - 1];
if (r->n != 0 && sc > 1 && r->n->to == f[sc - 2]) r->n = r->n->next;
if (r->n != 0)
{
sa[sc] = (double)r->n->to->a;
sp[sc] = 123456789123456789.0;
f[sc++] = r->n->to;
r->n->to->n = r->n->to->c;
r->n = r->n->next;
++r->cc;
}
else
{
--sc;
if (r->cc == 0) r->p = 0;
else r->p = (long long)sp[sc];
__m256d m = _mm256_set1_pd((double)r->b);
__m256d a = _mm256_set1_pd((double)r->p);
int i = 0;
if (sc - 200 > 0) i = (sc - 200) & ~3;
__m256d* qp = (__m256d*)&sp[i];
__m256d* qa = (__m256d*)&sa[i];
for (; i < sc; i += 4)
{
*qp = _mm256_min_pd(*qp, _mm256_add_pd(_mm256_mul_pd(*qa, m), a));
++qp, ++qa;
}
}
}
}
char NextChar()
{
static unsigned short pos;
static char buf[64 << 10];
if (pos == 0) fread(buf, 1, sizeof(buf), stdin);
return buf[pos++];
}
int NextInt()
{
char c = NextChar();
while (isspace(c)) c = NextChar();
int sign = 1;
if (c == '-') sign = -1, c = NextChar();
int res = 0;
while (isdigit(c))
{
res = res * 10 + c - '0';
c = NextChar();
}
return res * sign;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
int n = NextInt();
for (int i = 0; i < n; i++) v[i].a = NextInt();
for (int i = 0; i < n; i++) v[i].b = NextInt();
for (int i = 0; i < n - 1; i++)
{
int u = NextInt() - 1;
int v = NextInt() - 1;
AddEdge(::v[u], ::v[v]);
AddEdge(::v[v], ::v[u]);
}
Calc();
char buf[32];
for (int i = 0; i < n; i++)
puts(_i64toa(v[i].p, buf, 10));
return 0;
}
Submission ID: 35514985
-----------------------
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <intrin.h>
long long min(const long long& a, const long long& b)
{
return a <= b ? a : b;
}
struct V;
struct E;
const int m = 32;
struct V
{
long long p;
E* c;
E* n;
int a;
int b;
int cc;
} v[100000], *f[100000];
int sc = 0;
__declspec(align(32)) double sa[100002];
__declspec(align(32)) double sp[100002];
struct E
{
E* next;
V* to;
} e[200000];
int ec = 0;
void AddEdge(V& a, V& b)
{
E* ae = &e[ec++];
ae->to = &b;
ae->next = a.c;
a.c = ae;
}
long long changes = 0;
void Calc()
{
sa[sc] = (double)v->a;
sp[sc] = 123456789123456789.0;
f[sc++] = v;
v->n = v->c;
while (sc >= 1)
{
V* r = f[sc - 1];
if (r->n != 0 && sc > 1 && r->n->to == f[sc - 2]) r->n = r->n->next;
if (r->n != 0)
{
sa[sc] = (double)r->n->to->a;
sp[sc] = 123456789123456789.0;
f[sc++] = r->n->to;
r->n->to->n = r->n->to->c;
r->n = r->n->next;
++r->cc;
}
else
{
--sc;
if (r->cc == 0) r->p = 0;
else r->p = (long long)sp[sc];
__m256d m = _mm256_set1_pd((double)r->b);
__m256d a = _mm256_set1_pd((double)r->p);
int i = 0;
if (sc - 100 > 0) i = (sc - 100) & ~3;
__m256d* qp = (__m256d*)&sp[i];
__m256d* qa = (__m256d*)&sa[i];
for (; i < sc; i += 4)
{
*qp = _mm256_min_pd(*qp, _mm256_add_pd(_mm256_mul_pd(*qa, m), a));
++qp, ++qa;
}
}
}
}
char NextChar()
{
static unsigned short pos;
static char buf[64 << 10];
if (pos == 0) fread(buf, 1, sizeof(buf), stdin);
return buf[pos++];
}
int NextInt()
{
char c = NextChar();
while (isspace(c)) c = NextChar();
int sign = 1;
if (c == '-') sign = -1, c = NextChar();
int res = 0;
while (isdigit(c))
{
res = res * 10 + c - '0';
c = NextChar();
}
return res * sign;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
int n = NextInt();
for (int i = 0; i < n; i++) v[i].a = NextInt();
for (int i = 0; i < n; i++) v[i].b = NextInt();
for (int i = 0; i < n - 1; i++)
{
int u = NextInt() - 1;
int v = NextInt() - 1;
AddEdge(::v[u], ::v[v]);
AddEdge(::v[v], ::v[u]);
}
Calc();
char buf[32];
for (int i = 0; i < n; i++)
puts(_i64toa(v[i].p, buf, 10));
return 0;
}
Submission ID: 35515000
-----------------------
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <intrin.h>
long long min(const long long& a, const long long& b)
{
return a <= b ? a : b;
}
struct V;
struct E;
const int m = 32;
struct V
{
long long p;
E* c;
E* n;
int a;
int b;
int cc;
} v[100000], *f[100000];
int sc = 0;
__declspec(align(32)) double sa[100002];
__declspec(align(32)) double sp[100002];
struct E
{
E* next;
V* to;
} e[200000];
int ec = 0;
void AddEdge(V& a, V& b)
{
E* ae = &e[ec++];
ae->to = &b;
ae->next = a.c;
a.c = ae;
}
long long changes = 0;
void Calc()
{
sa[sc] = (double)v->a;
sp[sc] = 123456789123456789.0;
f[sc++] = v;
v->n = v->c;
while (sc >= 1)
{
V* r = f[sc - 1];
if (r->n != 0 && sc > 1 && r->n->to == f[sc - 2]) r->n = r->n->next;
if (r->n != 0)
{
sa[sc] = (double)r->n->to->a;
sp[sc] = 123456789123456789.0;
f[sc++] = r->n->to;
r->n->to->n = r->n->to->c;
r->n = r->n->next;
++r->cc;
}
else
{
--sc;
if (r->cc == 0) r->p = 0;
else r->p = (long long)sp[sc];
__m256d m = _mm256_set1_pd((double)r->b);
__m256d a = _mm256_set1_pd((double)r->p);
int i = 0;
if (sc - 50 > 0) i = (sc - 50) & ~3;
__m256d* qp = (__m256d*)&sp[i];
__m256d* qa = (__m256d*)&sa[i];
for (; i < sc; i += 4)
{
*qp = _mm256_min_pd(*qp, _mm256_add_pd(_mm256_mul_pd(*qa, m), a));
++qp, ++qa;
}
}
}
}
char NextChar()
{
static unsigned short pos;
static char buf[64 << 10];
if (pos == 0) fread(buf, 1, sizeof(buf), stdin);
return buf[pos++];
}
int NextInt()
{
char c = NextChar();
while (isspace(c)) c = NextChar();
int sign = 1;
if (c == '-') sign = -1, c = NextChar();
int res = 0;
while (isdigit(c))
{
res = res * 10 + c - '0';
c = NextChar();
}
return res * sign;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
int n = NextInt();
for (int i = 0; i < n; i++) v[i].a = NextInt();
for (int i = 0; i < n; i++) v[i].b = NextInt();
for (int i = 0; i < n - 1; i++)
{
int u = NextInt() - 1;
int v = NextInt() - 1;
AddEdge(::v[u], ::v[v]);
AddEdge(::v[v], ::v[u]);
}
Calc();
char buf[32];
for (int i = 0; i < n; i++)
puts(_i64toa(v[i].p, buf, 10));
return 0;
}
Submission ID: 35515087
-----------------------
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <intrin.h>
long long min(const long long& a, const long long& b)
{
return a <= b ? a : b;
}
struct V;
struct E;
const int m = 32;
struct V
{
long long p;
E* c;
E* n;
int a;
int b;
int cc;
} v[100000], *f[100000];
int sc = 0;
__declspec(align(32)) double sa[100002];
__declspec(align(32)) double sp[100002];
struct E
{
E* next;
V* to;
} e[200000];
int ec = 0;
void AddEdge(V& a, V& b)
{
E* ae = &e[ec++];
ae->to = &b;
ae->next = a.c;
a.c = ae;
}
long long changes = 0;
void Calc()
{
sa[sc] = (double)v->a;
sp[sc] = 123456789123456789.0;
f[sc++] = v;
v->n = v->c;
while (sc >= 1)
{
V* r = f[sc - 1];
if (r->n != 0 && sc > 1 && r->n->to == f[sc - 2]) r->n = r->n->next;
if (r->n != 0)
{
sa[sc] = (double)r->n->to->a;
sp[sc] = 123456789123456789.0;
f[sc++] = r->n->to;
r->n->to->n = r->n->to->c;
r->n = r->n->next;
++r->cc;
}
else
{
--sc;
if (r->cc == 0) r->p = 0;
else r->p = (long long)sp[sc];
__m256d m = _mm256_set1_pd((double)r->b);
__m256d a = _mm256_set1_pd((double)r->p);
int i = 0;
if (sc - 30 > 0) i = (sc - 30) & ~3;
__m256d* qp = (__m256d*)&sp[i];
__m256d* qa = (__m256d*)&sa[i];
for (; i < sc; i += 4)
{
*qp = _mm256_min_pd(*qp, _mm256_add_pd(_mm256_mul_pd(*qa, m), a));
++qp, ++qa;
}
}
}
}
char NextChar()
{
static unsigned short pos;
static char buf[64 << 10];
if (pos == 0) fread(buf, 1, sizeof(buf), stdin);
return buf[pos++];
}
int NextInt()
{
char c = NextChar();
while (isspace(c)) c = NextChar();
int sign = 1;
if (c == '-') sign = -1, c = NextChar();
int res = 0;
while (isdigit(c))
{
res = res * 10 + c - '0';
c = NextChar();
}
return res * sign;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
int n = NextInt();
for (int i = 0; i < n; i++) v[i].a = NextInt();
for (int i = 0; i < n; i++) v[i].b = NextInt();
for (int i = 0; i < n - 1; i++)
{
int u = NextInt() - 1;
int v = NextInt() - 1;
AddEdge(::v[u], ::v[v]);
AddEdge(::v[v], ::v[u]);
}
Calc();
char buf[32];
for (int i = 0; i < n; i++)
puts(_i64toa(v[i].p, buf, 10));
return 0;
}
Submission ID: 35515439
-----------------------
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <intrin.h>
long long min(const long long& a, const long long& b)
{
return a <= b ? a : b;
}
struct V;
struct E;
const int m = 32;
struct V
{
long long p;
E* c;
E* n;
int a;
int b;
int cc;
} v[100000], *f[100000];
int sc = 0;
__declspec(align(32)) double sa[100002];
__declspec(align(32)) double sp[100002];
struct E
{
E* next;
V* to;
} e[200000];
int ec = 0;
void AddEdge(V& a, V& b)
{
E* ae = &e[ec++];
ae->to = &b;
ae->next = a.c;
a.c = ae;
}
long long changes = 0;
void Calc()
{
sa[sc] = (double)v->a;
sp[sc] = 123456789123456789.0;
f[sc++] = v;
v->n = v->c;
while (sc >= 1)
{
V* r = f[sc - 1];
if (r->n != 0 && sc > 1 && r->n->to == f[sc - 2]) r->n = r->n->next;
if (r->n != 0)
{
sa[sc] = (double)r->n->to->a;
sp[sc] = 123456789123456789.0;
f[sc++] = r->n->to;
r->n->to->n = r->n->to->c;
r->n = r->n->next;
++r->cc;
}
else
{
--sc;
if (r->cc == 0) r->p = 0;
else r->p = (long long)sp[sc];
__m256d m = _mm256_set1_pd((double)r->b);
__m256d a = _mm256_set1_pd((double)r->p);
int i = 0;
if (sc - 1000 > 0) i = (sc - 1000) & ~3;
__m256d* qp = (__m256d*)&sp[i];
__m256d* qa = (__m256d*)&sa[i];
for (; i < sc; i += 4)
{
*qp = _mm256_min_pd(*qp, _mm256_add_pd(_mm256_mul_pd(*qa, m), a));
++qp, ++qa;
}
i = 0;
qp = (__m256d*)&sp[i];
qa = (__m256d*)&sa[i];
for (; i < min(1000, sc); i += 4)
{
*qp = _mm256_min_pd(*qp, _mm256_add_pd(_mm256_mul_pd(*qa, m), a));
++qp, ++qa;
}
}
}
}
char NextChar()
{
static unsigned short pos;
static char buf[64 << 10];
if (pos == 0) fread(buf, 1, sizeof(buf), stdin);
return buf[pos++];
}
int NextInt()
{
char c = NextChar();
while (isspace(c)) c = NextChar();
int sign = 1;
if (c == '-') sign = -1, c = NextChar();
int res = 0;
while (isdigit(c))
{
res = res * 10 + c - '0';
c = NextChar();
}
return res * sign;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
int n = NextInt();
for (int i = 0; i < n; i++) v[i].a = NextInt();
for (int i = 0; i < n; i++) v[i].b = NextInt();
for (int i = 0; i < n - 1; i++)
{
int u = NextInt() - 1;
int v = NextInt() - 1;
AddEdge(::v[u], ::v[v]);
AddEdge(::v[v], ::v[u]);
}
Calc();
char buf[32];
for (int i = 0; i < n; i++)
puts(_i64toa(v[i].p, buf, 10));
return 0;
}
Submission ID: 35940921
-----------------------
#include <bits/stdc++.h>
using ll = long long;
using pii = std::pair<int, int>;
bool cmp(const pii &A, const pii &B) {
if (A.second == B.second) {
return A.first < B.first;
}
return A.second < B.second;
}
const int maxn=1e5 + 4;
int n, m;
int cnt[maxn];
int dmax[maxn], dmin[maxn];
int pmax[maxn], pmin[maxn];
int main() {
std::vector<pii> ends;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) {
int l, r;
scanf("%d%d", &l, &r);
ends.emplace_back(0, l);
ends.emplace_back(1, r);
}
std::sort(ends.begin(), ends.end(), cmp);
int cur_cnt = 0;
int cur_end = 0;
for (int i = 1; i <= m; ++i) {
while (cur_end < ends.size() && ends[cur_end].second == i && ends[cur_end].first == 0) {
cur_cnt++;
cur_end++;
}
cnt[i] = cur_cnt;
while (cur_end < ends.size() && ends[cur_end].second == i && ends[cur_end].first == 1) {
cur_cnt--;
cur_end++;
}
}
dmax[0] = -1;
dmin[0] = -1;
for (int i = 1; i < maxn; ++i) {
dmin[i] = maxn;
dmax[i] = maxn;
}
int cur_mmax = 0, cur_mmin = 0;
for (int i = 1; i <= m; ++i) {
// dmax
int l = 0, r = maxn;
while (r - l > 1) {
int m = (r + l) / 2;
if (dmax[m] > cnt[i]) {
r = m;
} else {
l = m;
}
}
dmax[r] = cnt[i];
if (r > cur_mmax) {
cur_mmax = r;
}
pmax[i] = cur_mmax;
}
for (int i = m; i >= 1; --i) {
// dmin
int l = 0, r = maxn;
while (r - l > 1) {
int m = (r + l) / 2;
if (dmin[m] > cnt[i]) {
r = m;
} else {
l = m;
}
}
dmin[r] = cnt[i];
if (r > cur_mmin) {
cur_mmin = r;
}
pmin[i] = cur_mmin;
}
int ans = 0;
for (int i = 1; i < m; ++i) {
if (pmax[i] + pmin[i + 1] > ans) {
ans = pmax[i] + pmin[i + 1];
}
}
printf("%d\n", ans);
}
Submission ID: 35942029
-----------------------
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
def get_mm(a):
mmin = 1000000
mmax = -1000000
for el in a:
if el> mmax:
mmax = el
if el< mmin:
mmin = el
if mmax - mmin == 2:
break
return mmin, mmax
def sol(a):
b = []
mmin, mmax = get_mm(a)
if mmax - mmin != 2:
return len(a), a
'''if mmax - mmin == 1:
counter = Counter(a)
if counter.get(mmax) > counter.get(mmin):
k = counter.get(mmax)//2
b.extend([mmin] * counter.get(mmin))
b.extend([mmax+1] * k)
b.extend([mmax-1] * k)
b.extend([mmax] * (counter.get(mmax) - 2*k))
else:
k = counter.get(mmin) // 2
b.extend([mmax] * counter.get(mmax))
b.extend([mmin + 1] * k)
b.extend([mmin - 1] * k)
b.extend([mmin] * (counter.get(mmin) - 2 * k))
return len(a) - 2 * k, b
'''
mid_v = mmin + 1
counter = Counter(a)
one = min(counter.get(mmin), counter.get(mmax))
two = counter.get(mmin+1)//2
if one > two:
b.extend([mmin+1] * ((one*2) + counter.get(mmin+1)))
b.extend([mmax] * (counter.get(mmax) - one))
b.extend([mmin] * (counter.get(mmin) - one))
else:
b.extend([mmin+1] * (counter.get(mmin+1) - two*2))
b.extend([mmax] * (counter.get(mmax) + two))
b.extend([mmin] * (counter.get(mmin) + two ))
return len(a)- 2* max(one, two) , b
ans, mas = sol(a)
print(ans)
print(' '.join(list(map(str, mas))))
Submission ID: 35955986
-----------------------
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
def get_mm(a):
mmin = 1000000
mmax = -1000000
for el in a:
if el> mmax:
mmax = el
if el< mmin:
mmin = el
if mmax - mmin == 2:
break
return mmin, mmax
def sol(a):
b = []
mmin, mmax = get_mm(a)
if mmax - mmin != 2:
return len(a), a
'''if mmax - mmin == 1:
counter = Counter(a)
if counter.get(mmax) > counter.get(mmin):
k = counter.get(mmax)//2
b.extend([mmin] * counter.get(mmin))
b.extend([mmax+1] * k)
b.extend([mmax-1] * k)
b.extend([mmax] * (counter.get(mmax) - 2*k))
else:
k = counter.get(mmin) // 2
b.extend([mmax] * counter.get(mmax))
b.extend([mmin + 1] * k)
b.extend([mmin - 1] * k)
b.extend([mmin] * (counter.get(mmin) - 2 * k))
return len(a) - 2 * k, b
'''
mid_v = mmin + 1
counter = Counter(a)
if not counter.get(mmin+1):
counter[mmin+1] = 0
one = min(counter.get(mmin), counter.get(mmax))
two = counter.get(mmin+1)//2
if one > two:
b.extend([mmin+1] * ((one*2) + counter.get(mmin+1)))
b.extend([mmax] * (counter.get(mmax) - one))
b.extend([mmin] * (counter.get(mmin) - one))
else:
b.extend([mmin+1] * (counter.get(mmin+1) - two*2))
b.extend([mmax] * (counter.get(mmax) + two))
b.extend([mmin] * (counter.get(mmin) + two ))
return len(a)- 2* max(one, two) , b
ans, mas = sol(a)
print(ans)
print(' '.join(list(map(str, mas))))
Submission ID: 36115414
-----------------------
#include <iostream>
#include <cstdio>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <stdlib.h>
#include <functional>
#include <string>
#include <list>
#include <fstream>
#include <iomanip>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b) ((a >> b) & 1)
#define bitset(a,b) ( a |= (1 << b))
#define bitunset(a,b) (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#include <nmmintrin.h>
#ifdef _MSC_VER
#define __builtin_popcount _mm_popcnt_u32
#define __builtin_popcountll _mm_popcnt_u64
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
std::fill((T*)array, (T*)(array + N), val);
}
struct Edge {
int from, to;
};
ll func(ll n, ll tar) {
if (n % 2) {
if (tar % 2) return tar;
ll nt = tar / 2 - 1;
if (nt == 0) nt += n / 2;
return n + 1 + func(n / 2, nt);
}
else {
if (tar % 2) return tar;
ll nt = tar / 2;
return n + func(n / 2, nt);
}
}
int main() {
int n, q;
cin >> n >> q;
REP(i, q) {
ll buf;
scanf("%lld", &buf);
printf("%lld\n", (func(n,buf) + 1)/2);
}
return 0;
}
Submission ID: 36115558
-----------------------
#include <iostream>
#include <cstdio>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <stdlib.h>
#include <functional>
#include <string>
#include <list>
#include <fstream>
#include <iomanip>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b) ((a >> b) & 1)
#define bitset(a,b) ( a |= (1 << b))
#define bitunset(a,b) (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#include <nmmintrin.h>
#ifdef _MSC_VER
#define __builtin_popcount _mm_popcnt_u32
#define __builtin_popcountll _mm_popcnt_u64
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
std::fill((T*)array, (T*)(array + N), val);
}
struct Edge {
int from, to;
};
ll func(ll n, ll tar) {
if (n % 2) {
if (tar % 2) return tar;
ll nt = tar / 2 - 1;
if (nt == 0) nt += n / 2;
return n + 1 + func(n / 2, nt);
}
else {
if (tar % 2) return tar;
ll nt = tar / 2;
return n + func(n / 2, nt);
}
}
int main() {
ll n, q;
cin >> n >> q;
REP(i, q) {
ll buf;
scanf("%lld", &buf);
printf("%lld\n", (func(n,buf) + 1)/2);
}
return 0;
}
Submission ID: 36168307
-----------------------
#include <iostream>
#include <cstdio>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <stdlib.h>
#include <functional>
#include <string>
#include <list>
#include <fstream>
#include <iomanip>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b) ((a >> b) & 1)
#define bitset(a,b) ( a |= (1 << b))
#define bitunset(a,b) (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#include <nmmintrin.h>
#ifdef _MSC_VER
#define __builtin_popcount _mm_popcnt_u32
#define __builtin_popcountll _mm_popcnt_u64
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
std::fill((T*)array, (T*)(array + N), val);
}
struct Edge {
int from, to;
};
class Trie {
public:
Trie* next[2] = {NULL,NULL};
int cou = 0;
void insert(int x, int d = 29) {
if (d == -1) {
cou++;
return;
}
int c = bitcheck(x, d);
if (next[c] == NULL) next[c] = new Trie;
next[c]->insert(x,d-1);
}
bool use(int x, int cur = 0, int d = 29) {
if (d == -1) {
cout << (cur ^ x) << " ";
cou--;
return cou > 0;
}
int c = bitcheck(x, d);
if (next[c] == NULL) {
c = 1 - c;
}
if (c)
bitset(cur, d);
bool ret = next[c]->use(x, cur, d - 1);
if (!ret) {
next[c] = NULL;
}
if (next[0] == NULL && next[1] == NULL)
return false;
return true;
}
};
int main() {
int n;
cin >> n;
Trie trie;
vector<int> num(n);
REP(i, n) {
scnaf("%d", &num[i]);
}
REP(i, n) {
int buf;
scnaf("%d" ,& buf);
trie.insert(buf);
}
REP(i, n) {
trie.use(num[i]);
}
return 0;
}
Submission ID: 36241920
-----------------------
#include <iostream>
using namespace std;
struct time
{
int hh;
int mm;
time()
{
hh = 0;
mm = 0;
}
time (int _hh, int _mm)
{
hh = _hh;
mm = _mm;
}
time operator - (const time &arg) const
{
return time(hh - arg.hh, mm - arg.mm);
}
};
int x, y;
time wake;
time timed(time t)
{
while (t.mm < 0)
{
t.mm += 60;
--t.hh;
}
return t;
}
bool has_seven(time t)
{
if (t.hh % 10 == 7 || t.hh / 10 == 7 || t.mm % 10 == 7 || t.mm / 10 == 7)
return 1;
return 0;
}
int main()
{
cin >> x >> wake.hh >> wake.mm;
while (!has_seven(wake))
{
wake = timed(wake - time(0, x));
++y;
}
cout << y;
return 0;
}
Submission ID: 36242382
-----------------------
#include <iostream>
using namespace std;
struct time
{
int hh;
int mm;
time()
{
hh = 0;
mm = 0;
}
time (int _hh, int _mm)
{
hh = _hh;
mm = _mm;
}
};
int x, y;
time wake;
int main()
{
cin >> x >> wake.hh >> wake.mm;
while (wake.hh % 10 != 7 && wake.hh / 10 != 7 && wake.mm % 10 != 7 && wake.mm / 10 != 7)
{
wake.mm -= x;
while (wake.mm < 0)
{
wake.mm += 60;
--wake.hh;
if (wake.hh < 0)
wake.hh += 24;
}
++y;
}
cout << y;
return 0;
}
Submission ID: 36517778
-----------------------
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<unsigned> vu;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef pair<int, int> pii;
typedef pair<unsigned, unsigned> puu;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef vector<string> vs;
#define pb push_back
#define ppb pop_back
#define be begin
#define all(x) (x).be(), (x).end()
#define fst first
#define fir first
#define sec second
#define mkp make_pair
#define brif(cond) if (cond) break
#define ctif(cond) if (cond) continue
#define retif(cond) if (cond) return
static inline void canhazfast() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);}
template<typename T> T gcd(T a, T b) {return b == 0 ? a : gcd(b, a%b);}
template<typename T> T extgcd(T a, T b, T &x, T &y)
{
T x0 = 1, y0 = 0, x1 = 0, y1 = 1;
while (b) {
T q = a/b; a %= b; swap(a, b);
x0 -= q*x1; swap(x0, x1);
y0 -= q*y1; swap(y0, y1);
}
x = x0; y = y0; return a;
}
#define MOD 1000000007
#define mul(a, b) (ull(a)*(b)%MOD)
#define add(a, b) ((a)+(b) >= MOD ? (a)+(b)-MOD : (a)+(b))
#define sub(a, b) ((a) < (b) ? (a)+MOD-(b) : (a)-(b))
void mul_mm(unsigned a[][4], unsigned b[][4], unsigned r[][4])
{
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
r[i][j] = mul(a[i][0], b[0][j]);
r[i][j] = add(r[i][j], mul(a[i][1], b[1][j]));
r[i][j] = add(r[i][j], mul(a[i][2], b[2][j]));
}
}
}
void mul_mv(unsigned a[][4], const unsigned v[], unsigned r[])
{
/*cout << "mul_mv:\nm = \n";
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) cout << ' ' << a[i][j];
cout << '\n';
}
cout << "v =";
for (int i = 0; i < 3; ++i) cout << ' ' << v[i];
cout << '\n';*/
for (int i = 0; i < 3; ++i) {
r[i] = mul(a[i][0], v[0]);
r[i] = add(r[i], mul(a[i][1], v[1]));
r[i] = add(r[i], mul(a[i][2], v[2]));
}
/*cout << "r =";
for (int i = 0; i < 3; ++i) cout << ' ' << r[i];
cout << "\n\n";*/
}
void mcpy(unsigned a[][4], unsigned r[][4])
{
copy_n(a[0], 12, r[0]);
}
void pow_m(unsigned b[][4], ull e, unsigned r[][4])
{
/*cout << "matrix power: e = " << e << '\n';
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) cout << ' ' << b[i][j];
cout << '\n';
}*/
unsigned tmp[3][4];
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) r[i][j] = i == j ? 1 : 0;
}
while (e) {
if (e&1) {
mul_mm(b, r, tmp);
mcpy(tmp, r);
}
mul_mm(b, b, tmp);
mcpy(tmp, b);
e >>= 1;
}
/*cout << "gives:\n";
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) cout << ' ' << r[i][j];
cout << '\n';
}
cout << '\n';*/
}
void gen(int msk, unsigned a[][4])
{
//cout << "gen(" << msk << "):\n";
a[0][0] = a[0][1] = msk&1; a[0][2] = 0;
msk >>= 1;
a[1][0] = a[1][1] = a[1][2] = msk&1;
msk >>= 1;
a[2][0] = 0; a[2][1] = a[2][2] = msk&1;
/*for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) cout << ' ' << a[i][j];
cout << '\n';
}
cout << '\n';*/
}
void step(unsigned v[], int msk, ull len)
{
unsigned t[2][3][4];
unsigned vt[4];
gen(msk, t[0]);
pow_m(t[0], len, t[1]);
mul_mv(t[1], v, vt);
copy_n(vt, 4, v);
}
struct S {
ull l, r;
int msk;
};
bool cmp(const S &a, const S &b)
{
return a.l > b.l || (a.l == b.l && a.r > b.r);
}
int main()
{
canhazfast();
int n;
ull m, p = 1;
unsigned v[4] = {0, 1, 0};
vector<S> ob;
cin >> n >> m;
ob.resize(n);
for (int i = 0; i < n; ++i) {
int a;
cin >> a >> ob[i].l >> ob[i].r;
ob[i].msk = 7^(1 << (a-1));
}
priority_queue<S, vector<S>, decltype(&cmp)> q(&cmp, move(ob));
while (!q.empty()) {
S cur = q.top();
q.pop();
while (!q.empty() && q.top().l <= cur.r) {
S nxt = q.top();
q.pop();
if (nxt.l == cur.l) {
cur.msk &= nxt.msk;
if (nxt.r > cur.r) q.push({cur.r+1, nxt.r, nxt.msk});
} else {
q.push({nxt.l, min(cur.r, nxt.r), cur.msk&nxt.msk});
if (nxt.r < cur.r) q.push({nxt.r+1, cur.r, cur.msk});
else if (nxt.r > cur.r) q.push({cur.r+1, nxt.r, nxt.msk});
cur.r = nxt.l-1;
}
}
//cout << "d " << cur.l << ' ' << cur.r << ' ' << cur.msk << '\n';
if (p+1 < cur.l) step(v, 7, cur.l-p-1);
step(v, cur.msk, cur.r+1-cur.l);
p = cur.r;
}
if (p < m) step(v, 7, m-p);
cout << v[1] << '\n';
//for (int i = 0; i < 3; ++i) cout << "v(" << i << ") = " << v[i] << '\n';
return 0;
}
Submission ID: 36517796
-----------------------
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<unsigned> vu;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef pair<int, int> pii;
typedef pair<unsigned, unsigned> puu;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef vector<string> vs;
#define pb push_back
#define ppb pop_back
#define be begin
#define all(x) (x).be(), (x).end()
#define fst first
#define fir first
#define sec second
#define mkp make_pair
#define brif(cond) if (cond) break
#define ctif(cond) if (cond) continue
#define retif(cond) if (cond) return
static inline void canhazfast() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);}
template<typename T> T gcd(T a, T b) {return b == 0 ? a : gcd(b, a%b);}
template<typename T> T extgcd(T a, T b, T &x, T &y)
{
T x0 = 1, y0 = 0, x1 = 0, y1 = 1;
while (b) {
T q = a/b; a %= b; swap(a, b);
x0 -= q*x1; swap(x0, x1);
y0 -= q*y1; swap(y0, y1);
}
x = x0; y = y0; return a;
}
#define MOD 1000000007
#define mul(a, b) (ull(a)*(b)%MOD)
#define add(a, b) ((a)+(b) >= MOD ? (a)+(b)-MOD : (a)+(b))
#define sub(a, b) ((a) < (b) ? (a)+MOD-(b) : (a)-(b))
void mul_mm(unsigned a[][4], unsigned b[][4], unsigned r[][4])
{
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
r[i][j] = mul(a[i][0], b[0][j]);
r[i][j] = add(r[i][j], mul(a[i][1], b[1][j]));
r[i][j] = add(r[i][j], mul(a[i][2], b[2][j]));
}
}
}
void mul_mv(unsigned a[][4], const unsigned v[], unsigned r[])
{
/*cout << "mul_mv:\nm = \n";
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) cout << ' ' << a[i][j];
cout << '\n';
}
cout << "v =";
for (int i = 0; i < 3; ++i) cout << ' ' << v[i];
cout << '\n';*/
for (int i = 0; i < 3; ++i) {
r[i] = mul(a[i][0], v[0]);
r[i] = add(r[i], mul(a[i][1], v[1]));
r[i] = add(r[i], mul(a[i][2], v[2]));
}
/*cout << "r =";
for (int i = 0; i < 3; ++i) cout << ' ' << r[i];
cout << "\n\n";*/
}
void mcpy(unsigned a[][4], unsigned r[][4])
{
copy_n(a[0], 12, r[0]);
}
void pow_m(unsigned b[][4], ull e, unsigned r[][4])
{
/*cout << "matrix power: e = " << e << '\n';
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) cout << ' ' << b[i][j];
cout << '\n';
}*/
unsigned tmp[3][4];
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) r[i][j] = i == j ? 1 : 0;
}
while (e) {
if (e&1) {
mul_mm(b, r, tmp);
mcpy(tmp, r);
}
mul_mm(b, b, tmp);
mcpy(tmp, b);
e >>= 1;
}
/*cout << "gives:\n";
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) cout << ' ' << r[i][j];
cout << '\n';
}
cout << '\n';*/
}
void gen(int msk, unsigned a[][4])
{
//cout << "gen(" << msk << "):\n";
a[0][0] = a[0][1] = msk&1; a[0][2] = 0;
msk >>= 1;
a[1][0] = a[1][1] = a[1][2] = msk&1;
msk >>= 1;
a[2][0] = 0; a[2][1] = a[2][2] = msk&1;
/*for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) cout << ' ' << a[i][j];
cout << '\n';
}
cout << '\n';*/
}
void step(unsigned v[], int msk, ull len)
{
unsigned t[2][3][4];
unsigned vt[4];
gen(msk, t[0]);
pow_m(t[0], len, t[1]);
mul_mv(t[1], v, vt);
copy_n(vt, 4, v);
}
struct S {
ull l, r;
int msk;
};
bool cmp(const S &a, const S &b)
{
return a.l > b.l || (a.l == b.l && a.r > b.r);
}
int main()
{
canhazfast();
int n;
ull m, p = 1;
unsigned v[4] = {0, 1, 0};
vector<S> ob;
cin >> n >> m;
ob.resize(n);
for (int i = 0; i < n; ++i) {
int a;
cin >> a >> ob[i].l >> ob[i].r;
ob[i].msk = 7^(1 << (a-1));
}
priority_queue<S, vector<S>, decltype(&cmp)> q(&cmp, move(ob));
while (!q.empty()) {
S cur = q.top();
q.pop();
if (!q.empty() && q.top().l <= cur.r) {
S nxt = q.top();
q.pop();
if (nxt.l == cur.l) {
cur.msk &= nxt.msk;
if (nxt.r > cur.r) q.push({cur.r+1, nxt.r, nxt.msk});
} else {
q.push({nxt.l, min(cur.r, nxt.r), cur.msk&nxt.msk});
if (nxt.r < cur.r) q.push({nxt.r+1, cur.r, cur.msk});
else if (nxt.r > cur.r) q.push({cur.r+1, nxt.r, nxt.msk});
cur.r = nxt.l-1;
}
}
//cout << "d " << cur.l << ' ' << cur.r << ' ' << cur.msk << '\n';
if (p+1 < cur.l) step(v, 7, cur.l-p-1);
step(v, cur.msk, cur.r+1-cur.l);
p = cur.r;
}
if (p < m) step(v, 7, m-p);
cout << v[1] << '\n';
//for (int i = 0; i < 3; ++i) cout << "v(" << i << ") = " << v[i] << '\n';
return 0;
}
Submission ID: 36517827
-----------------------
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<unsigned> vu;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef pair<int, int> pii;
typedef pair<unsigned, unsigned> puu;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef vector<string> vs;
#define pb push_back
#define ppb pop_back
#define be begin
#define all(x) (x).be(), (x).end()
#define fst first
#define fir first
#define sec second
#define mkp make_pair
#define brif(cond) if (cond) break
#define ctif(cond) if (cond) continue
#define retif(cond) if (cond) return
static inline void canhazfast() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);}
template<typename T> T gcd(T a, T b) {return b == 0 ? a : gcd(b, a%b);}
template<typename T> T extgcd(T a, T b, T &x, T &y)
{
T x0 = 1, y0 = 0, x1 = 0, y1 = 1;
while (b) {
T q = a/b; a %= b; swap(a, b);
x0 -= q*x1; swap(x0, x1);
y0 -= q*y1; swap(y0, y1);
}
x = x0; y = y0; return a;
}
#define MOD 1000000007
#define mul(a, b) (ull(a)*(b)%MOD)
#define add(a, b) ((a)+(b) >= MOD ? (a)+(b)-MOD : (a)+(b))
#define sub(a, b) ((a) < (b) ? (a)+MOD-(b) : (a)-(b))
void mul_mm(unsigned a[][4], unsigned b[][4], unsigned r[][4])
{
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
r[i][j] = mul(a[i][0], b[0][j]);
r[i][j] = add(r[i][j], mul(a[i][1], b[1][j]));
r[i][j] = add(r[i][j], mul(a[i][2], b[2][j]));
}
}
}
void mul_mv(unsigned a[][4], const unsigned v[], unsigned r[])
{
/*cout << "mul_mv:\nm = \n";
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) cout << ' ' << a[i][j];
cout << '\n';
}
cout << "v =";
for (int i = 0; i < 3; ++i) cout << ' ' << v[i];
cout << '\n';*/
for (int i = 0; i < 3; ++i) {
r[i] = mul(a[i][0], v[0]);
r[i] = add(r[i], mul(a[i][1], v[1]));
r[i] = add(r[i], mul(a[i][2], v[2]));
}
/*cout << "r =";
for (int i = 0; i < 3; ++i) cout << ' ' << r[i];
cout << "\n\n";*/
}
void mcpy(unsigned a[][4], unsigned r[][4])
{
copy_n(a[0], 12, r[0]);
}
void pow_m(unsigned b[][4], ull e, unsigned r[][4])
{
/*cout << "matrix power: e = " << e << '\n';
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) cout << ' ' << b[i][j];
cout << '\n';
}*/
unsigned tmp[3][4];
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) r[i][j] = i == j ? 1 : 0;
}
while (e) {
if (e&1) {
mul_mm(b, r, tmp);
mcpy(tmp, r);
}
mul_mm(b, b, tmp);
mcpy(tmp, b);
e >>= 1;
}
/*cout << "gives:\n";
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) cout << ' ' << r[i][j];
cout << '\n';
}
cout << '\n';*/
}
void gen(int msk, unsigned a[][4])
{
//cout << "gen(" << msk << "):\n";
a[0][0] = a[0][1] = msk&1; a[0][2] = 0;
msk >>= 1;
a[1][0] = a[1][1] = a[1][2] = msk&1;
msk >>= 1;
a[2][0] = 0; a[2][1] = a[2][2] = msk&1;
/*for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) cout << ' ' << a[i][j];
cout << '\n';
}
cout << '\n';*/
}
void step(unsigned v[], int msk, ull len)
{
unsigned t[2][3][4];
unsigned vt[4];
gen(msk, t[0]);
if (len > 1) {
pow_m(t[0], len, t[1]);
mul_mv(t[1], v, vt);
} else {
mul_mv(t[0], v, vt);
}
copy_n(vt, 4, v);
}
struct S {
ull l, r;
int msk;
};
bool cmp(const S &a, const S &b)
{
return a.l > b.l || (a.l == b.l && a.r > b.r);
}
int main()
{
canhazfast();
int n;
ull m, p = 1;
unsigned v[4] = {0, 1, 0};
vector<S> ob;
cin >> n >> m;
ob.resize(n);
for (int i = 0; i < n; ++i) {
int a;
cin >> a >> ob[i].l >> ob[i].r;
ob[i].msk = 7^(1 << (a-1));
}
priority_queue<S, vector<S>, decltype(&cmp)> q(&cmp, move(ob));
while (!q.empty()) {
S cur = q.top();
q.pop();
while (!q.empty() && q.top().l <= cur.r) {
S nxt = q.top();
q.pop();
if (nxt.l == cur.l) {
cur.msk &= nxt.msk;
if (nxt.r > cur.r) q.push({cur.r+1, nxt.r, nxt.msk});
} else {
q.push({nxt.l, min(cur.r, nxt.r), cur.msk&nxt.msk});
if (nxt.r < cur.r) q.push({nxt.r+1, cur.r, cur.msk});
else if (nxt.r > cur.r) q.push({cur.r+1, nxt.r, nxt.msk});
cur.r = nxt.l-1;
}
}
if (p+1 < cur.l) step(v, 7, cur.l-p-1);
step(v, cur.msk, cur.r+1-cur.l);
p = cur.r;
if (!(v[0]||v[1]||v[2])) break;
}
if (p < m) step(v, 7, m-p);
cout << v[1] << '\n';
return 0;
}
Submission ID: 36529990
-----------------------
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<unsigned> vu;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef pair<int, int> pii;
typedef pair<unsigned, unsigned> puu;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef vector<string> vs;
#define pb push_back
#define ppb pop_back
#define be begin
#define all(x) (x).be(), (x).end()
#define fst first
#define fir first
#define sec second
#define mkp make_pair
#define brif(cond) if (cond) break
#define ctif(cond) if (cond) continue
#define retif(cond) if (cond) return
static inline void canhazfast() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);}
template<typename T> T gcd(T a, T b) {return b == 0 ? a : gcd(b, a%b);}
template<typename T> T extgcd(T a, T b, T &x, T &y)
{
T x0 = 1, y0 = 0, x1 = 0, y1 = 1;
while (b) {
T q = a/b; a %= b; swap(a, b);
x0 -= q*x1; swap(x0, x1);
y0 -= q*y1; swap(y0, y1);
}
x = x0; y = y0; return a;
}
#define MOD 1000000007
#define mul(a, b) (ull(a)*(b)%MOD)
#define add(a, b) ((a)+(b) >= MOD ? (a)+(b)-MOD : (a)+(b))
#define sub(a, b) ((a) < (b) ? (a)+MOD-(b) : (a)-(b))
void mul_mm(unsigned a[][4], unsigned b[][4], unsigned r[][4])
{
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
r[i][j] = mul(a[i][0], b[0][j]);
r[i][j] = add(r[i][j], mul(a[i][1], b[1][j]));
r[i][j] = add(r[i][j], mul(a[i][2], b[2][j]));
}
}
}
void mul_mv(unsigned a[][4], const unsigned v[], unsigned r[])
{
for (int i = 0; i < 3; ++i) {
r[i] = mul(a[i][0], v[0]);
r[i] = add(r[i], mul(a[i][1], v[1]));
r[i] = add(r[i], mul(a[i][2], v[2]));
}
}
void mcpy(unsigned a[][4], unsigned r[][4])
{
copy_n(a[0], 12, r[0]);
}
void pow_m(unsigned b[][4], ull e, unsigned r[][4])
{
unsigned tmp[3][4];
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) r[i][j] = i == j ? 1 : 0;
}
while (e) {
if (e&1) {
mul_mm(b, r, tmp);
mcpy(tmp, r);
}
mul_mm(b, b, tmp);
mcpy(tmp, b);
e >>= 1;
}
}
void gen_mat(int msk, unsigned a[][4])
{
a[0][0] = a[0][1] = msk&1; a[0][2] = 0;
msk >>= 1;
a[1][0] = a[1][1] = a[1][2] = msk&1;
msk >>= 1;
a[2][0] = 0; a[2][1] = a[2][2] = msk&1;
}
int gen_msk(const int c[])
{
//cout << "gen_msk:\n";
//cout << "\tcnt = " << c[0] << ' ' << c[1] << ' ' << c[2] << '\n';
int r = 1*!c[0]+2*!c[1]+4*!c[2];
//cout << "\tr = " << r << '\n';
return r;
}
void step(unsigned v[], int msk, ull len)
{
//cout << "step: msk = " << msk << ", len = " << len << '\n';
unsigned t[2][3][4];
unsigned vt[4];
gen_mat(msk, t[0]);
if (len > 1) {
pow_m(t[0], len, t[1]);
mul_mv(t[1], v, vt);
} else {
mul_mv(t[0], v, vt);
}
copy_n(vt, 4, v);
}
struct S {
ull p;
int a, st;
};
bool cmp(const S &a, const S &b)
{
return a.p < b.p;
}
int main()
{
canhazfast();
static S s[20016];
int n;
ull m, p = 1;
unsigned v[4] = {0, 1, 0};
int cnt[4] = {};
cin >> n >> m;
for (int i = 0; i < n; ++i) {
int a;
ull l, r;
cin >> a >> l >> r;
s[2*i] = {l-1, a-1, 1};
s[2*i+1] = {r, a-1, 0};
}
sort(s, s+2*n, cmp);
for (int i = 0; i < 2*n; ++i) {
if (s[i].p > p) step(v, gen_msk(cnt), s[i].p-p);
if (s[i].st) ++cnt[s[i].a];
else --cnt[s[i].a];
p = s[i].p;
}
if (m > p) step(v, gen_msk(cnt), m-p);
cout << v[1] << '\n';
return 0;
}
Submission ID: 36538447
-----------------------
#include <bits/stdc++.h>
using namespace std;
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i <= n; i++)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define V vector<int>
#define VP vector<pair<int, int> >
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define index INDEX
#ifdef _WIN32
#include <windows.h>
#define print(x) PRINT(x, #x)
template<typename T> inline const void PRINT(T VARIABLE, string NAME)
{
#ifndef ONLINE_JUDGE /// ONLINE_JUDGE IS DEFINED ON CODEFORCES
HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hConsole, 10);
cerr << NAME << " = " << VARIABLE;
SetConsoleTextAttribute(hConsole, 7);
cerr << '\n';
#endif
}
#else
#define print(x) 0
#endif
typedef long long ll;
typedef unsigned long long ull;
const ll INFLL = 2 * (ll)1e18 + 100;
const int INFINT = 2 * (int)1e9 + 100;
const double PI = atan(1) * 4;
const double EPS = 1e-9;
const int SEED = 1e3 + 7;
const int MOD = 1e9 + 7; /// careful here (7 or 9, 66.. etc)25000033
const int NMAX = 1e3 + 5;
string hh, mm;
ll current_hunger, increase_hunger, decrease_hunger;
double cost, sol = INFINT;
int main()
{
FASTIO;
cin >> hh >> mm;
cin >> current_hunger >> increase_hunger >> cost >> decrease_hunger;
if(hh < "20")
{
cerr << "here";
ll nr = current_hunger / decrease_hunger;
if(current_hunger % decrease_hunger) nr++;
sol = min(sol, cost * (double) nr);
while(hh != "20")
{
int first_mm = mm[0] - '0';
int last_mm = mm[1] - '0';
int first_hh = hh[0] - '0';
int last_hh = hh[1] - '0';
last_mm++;
if(last_mm == 10)
{
last_mm = 0;
first_mm++;
if(first_mm == 6)
{
last_hh++;
if(last_hh == 10) first_hh++;
last_hh %= 10;
first_mm = 0;
}
}
mm[0] = first_mm + '0';
mm[1] = last_mm + '0';
hh[0] = first_hh + '0';
hh[1] = last_hh + '0';
current_hunger += increase_hunger;
// cerr << hh << ' ' << mm << '\n';
}
}
if(hh >= "20")
{
cost = cost - cost * 20 / 100;
ll nr = current_hunger / decrease_hunger;
if(current_hunger % decrease_hunger) nr++;
sol = min(sol, cost * (double) nr);
return cout << setprecision(30) << fixed << sol, 0;
}
return 0;
}
Submission ID: 36542365
-----------------------
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int i,hh,mm;
cin>>hh>>mm;
double ans,ans1,h1;
double h,d,c,n;
cin>>h>>d>>c>>n;
if(h>=20 && h<=23)
{
ans=ceil(h/n);
ans=ans*c;
cout<<ans*0.80<<"\n";
}
else
{
double total_mm=hh*60+mm;
double p=60*20-total_mm;
h1=h+p*d;
ans1=ceil(h1/n);
ans1=ans1*c;
//cout<<ans1<<"\n";
ans=ceil(h/n);
ans=ans*c;
//cout<<ans<<"\n";
ans1=ans1*0.80;
cout<<min(ans,ans1)<<"\n";
}
return 0;
}
Submission ID: 36544531
-----------------------
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int i,hh,mm;
cin>>hh>>mm;
double ans,ans1,h1;
double h,d,c,n;
cin>>h>>d>>c>>n;
if(h>=20 && h<=23)
{
ans=ceil(h/n);
ans=ans*c;
printf("%.4f\n",ans*0.80);
}
else
{
double total_mm=hh*60+mm;
double p=60*20-total_mm;
h1=h+p*d;
ans1=ceil(h1/n);
ans1=ans1*c;
//cout<<ans1<<"\n";
ans=ceil(h/n);
ans=ans*c;
//cout<<ans<<"\n";
ans1=ans1*0.80;
printf("%.4f\n",min(ans,ans1));
}
return 0;
}
Submission ID: 36545510
-----------------------
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int i,hh,mm;
cin>>hh>>mm;
double ans,ans1,h1;
double h,d,c,n;
cin>>h>>d>>c>>n;
if(hh>=20 && hh<=23)
{
ans=ceil(h/n);
ans=ans*c;
printf("%.3lf\n",ans*0.80);
}
else
{
double total_mm=hh*60+mm;
double p=60*20-total_mm;
h1=h+p*d;
ans1=ceil(h1/n);
ans1=ans1*c;
//cout<<ans1<<"\n";
ans=ceil(h/n);
ans=ans*c;
//cout<<ans<<"\n";
ans1=ans1*0.80;
printf("%.3lf\n",min(ans,ans1));
}
return 0;
}
Submission ID: 36548786
-----------------------
def convert_to_mins(h, m):
return h * 60 + m
# count quantity of food
def count_food(hunger, decrise_val):
count_of_bread = 0;
while (hunger > 0):
hunger = hunger - decrise_val;
count_of_bread+=1
return count_of_bread
#result summ
def count_sum(quantity, cost_per_one, id):
result_summ = 0
#count with disc if 0
if(id == 0):
discount_val = cost_per_one/100 * 20
new_cost = cost_per_one - discount_val
result_summ = new_cost * quantity
elif(id == 1):
result_summ = quantity * cost_per_one
return result_summ
# cost if wait . COUNT WITH DISCOUNT
def cost_if_wait(def_time, adder_of_hungry_val, decrise_val, cost_per_one, hunger_current):
new_hunger = hunger_current + (def_time * adder_of_hungry_val)
# count food
bread = count_food(new_hunger, decrise_val)
# buy with discount
return count_sum(bread,cost_per_one, 0)
# ------------------- END OF FUNC BLOCK -------------------
#Enter hh & mm
hh_mm = list()
hh_mm = input()
splited_hh_mm = hh_mm.split()
hh = int(splited_hh_mm[0])
mm = int(splited_hh_mm[1])
#Enter 2nd row
h_d_c_n = list()
h_d_c_n = input()
splited_h_d_c_n = h_d_c_n.split()
hungry_of_cat = int(splited_h_d_c_n[0])
adder_of_hungry = int(splited_h_d_c_n[1])
cost = int(splited_h_d_c_n[2])
decrease_of_hungry = int(splited_h_d_c_n[3])
minutes_now = convert_to_mins(hh, mm)
minutes_begin_discount = convert_to_mins(20, 00)
minutes_end_discount = convert_to_mins(23, 59)
# count different between time
# If get up while discount - count with discount
if(minutes_now >= minutes_begin_discount & minutes_now <= minutes_end_discount):
quantity_of_bread = count_food(hungry_of_cat, decrease_of_hungry)
min_sum = count_sum(quantity_of_bread, cost, 0)
elif(minutes_now > minutes_end_discount):
# count different between time
delta_time = minutes_begin_discount - minutes_now
#if wait
cost_one = cost_if_wait(delta_time, adder_of_hungry, decrease_of_hungry, cost, hungry_of_cat)
#no wait
quantity_of_bread = count_food(hungry_of_cat, decrease_of_hungry)
cost_two = count_sum(quantity_of_bread, cost, 1)
min_sum = min(cost_one, cost_two)
print(min_sum)
Submission ID: 36549361
-----------------------
def convert_to_mins(h, m):
return h * 60 + m
# count quantity of food
def count_food(hunger, decrise_val):
count_of_bread = 0;
while (hunger > 0):
hunger = hunger - decrise_val;
count_of_bread+=1
return count_of_bread
#result summ
def count_sum(quantity, cost_per_one, id):
result_summ = 0
#count with disc if 0
if(id == 0):
discount_val = cost_per_one/100 * 20
new_cost = cost_per_one - discount_val
result_summ = new_cost * quantity
elif(id == 1):
result_summ = quantity * cost_per_one
return result_summ
# cost if wait . COUNT WITH DISCOUNT
def cost_if_wait(def_time, adder_of_hungry_val, decrise_val, cost_per_one, hunger_current):
new_hunger = hunger_current + (def_time * adder_of_hungry_val)
# count food
bread = count_food(new_hunger, decrise_val)
# buy with discount
return count_sum(bread,cost_per_one, 0)
# ------------------- END OF FUNC BLOCK -------------------
#Enter hh & mm
hh_mm = list()
hh_mm = input()
splited_hh_mm = hh_mm.split()
hh = int(splited_hh_mm[0])
mm = int(splited_hh_mm[1])
min_sum = 0
#Enter 2nd row
h_d_c_n = list()
h_d_c_n = input()
splited_h_d_c_n = h_d_c_n.split()
hungry_of_cat = int(splited_h_d_c_n[0])
adder_of_hungry = int(splited_h_d_c_n[1])
cost = int(splited_h_d_c_n[2])
decrease_of_hungry = int(splited_h_d_c_n[3])
minutes_now = convert_to_mins(hh, mm)
minutes_begin_discount = convert_to_mins(20, 00)
minutes_end_discount = convert_to_mins(23, 59)
# count different between time
# If get up while discount - count with discount
if(minutes_now >= minutes_begin_discount and minutes_now <= minutes_end_discount):
quantity_of_bread = count_food(hungry_of_cat, decrease_of_hungry)
min_sum = count_sum(quantity_of_bread, cost, 0)
elif(minutes_now < minutes_end_discount):
# count different between time
delta_time = minutes_begin_discount - minutes_now
#if wait
cost_one = cost_if_wait(delta_time, adder_of_hungry, decrease_of_hungry, cost, hungry_of_cat)
#no wait
quantity_of_bread = count_food(hungry_of_cat, decrease_of_hungry)
cost_two = count_sum(quantity_of_bread, cost, 1)
min_sum = min(cost_one, cost_two)
print(min_sum)
Submission ID: 36549992
-----------------------
#include <iostream>
using namespace std;
int diff_mm(int hh, int mm)
{
int total_mins = 0;
if(hh < 20)
{
if(mm > 0)
{
total_mins += (60 - mm);
}
total_mins += (20 - hh) * 60;
}
else
{
total_mins += (hh - 20) * 60 + mm;
}
return total_mins;
}
float money_case1(int hh, int mm, int H, int C, int N)
{
float money_1 = 0;
while(H > 0)
{
H -= N;
//money_1 += C;
if(mm == 59 && hh < 20)
{
mm = 0;
//hh++;
}
else if(mm == 59 && hh >= 20)
{
mm = 0;
hh++;
}
else
{
mm++;
}
if(hh < 20)
{
money_1 += C;
}
else
{
money_1 += 0.8 * float(C);
}
}
return money_1;
}
float money_case2(int hh, int mm, int H, int D, int C, int N)
{
float money_2 = 0;
H += D * diff_mm(hh,mm);
while(H > 0)
{
H -= N;
if(mm == 59)
{
mm = 0;
hh++;
}
else
{
mm++;
}
money_2 += 0.8 * C;
}
return money_2;
}
int main()
{
int hh, mm, H, D, C, N;
float min_money;
cin >> hh >> mm;
cin >> H >> D >> C >> N;
if(hh < 20)
{
float money_1 = money_case1(hh, mm, H, C, N);
float money_2 = money_case2(hh, mm, H, D, C, N);
min_money = (money_1 < money_2) ? money_1 : money_2;
}
else
{
min_money = money_case1(hh, mm, H, C, N);
}
cout << min_money << endl;
return 0;
}
Submission ID: 36598534
-----------------------
#ifdef _MSC_VER
#define _CRT_SECURE_NO_DEPRECATE
#pragma comment(linker, "/STACK:66777216")
#include <cstdio>
#define GETS gets_s
#else
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <stdio.h>
#define GETS gets
#endif
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <iostream>
#include <iterator>
#include <cmath>
#include <cstdlib>
#include <sstream>
#include <fstream>
#include <ctime>
#include <cstring>
#include <functional>
#include <chrono>
#include <intrin.h>
using namespace std;
#define pb push_back
#define ppb pop_back
#define pi 3.1415926535897932384626433832795028841971
#define mp make_pair
#define x first
#define y second
#define pii pair<int,int>
#define pdd pair<double,double>
#define INF 1000000000
#define FOR(i,a,b) for (int _n(b), i(a); i <= _n; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;i--)
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define rep(i,n) FOR(i,1,(n))
#define rept(i,n) FOR(i,0,(n)-1)
#define L(s) (int)((s).size())
#define C(a) memset((a),0,sizeof(a))
#define VI vector <int>
#define ll long long
#include <array>
// SSE2 optimized bitset
template<int N>
class Bitset {
public:
Bitset() : data(arr_.data()) {
reset();
}
Bitset<N>& operator=(const Bitset<N>& other) {
arr_ = other.arr_;
data = arr_.data();
return *this;
}
Bitset<N>(const Bitset<N>& other) {
arr_ = other.arr_;
data = arr_.data();
}
Bitset<N>& operator=(Bitset<N>&& other) {
arr_ = std::move(other.arr_);
data = arr_.data();
return *this;
}
Bitset<N>(Bitset<N>&& other) {
arr_ = std::move(other.arr_);
data = arr_.data();
}
inline void set() {
memset(data, 255, n * sizeof(unsigned));
}
inline void set(int pos) {
data[pos >> 5] |= 1u << (pos & 31);
}
inline void reset() {
memset(data, 0, n * sizeof(unsigned));
}
inline void reset(int pos) {
data[pos >> 5] &= ~(1u << (pos & 31));
}
inline void flip(int pos) {
data[pos >> 5] ^= 1u << (pos & 31);
}
inline bool test(int pos) const {
return (data[pos >> 5] >> (pos & 31)) & 1;
}
inline Bitset<N>& operator |=(const Bitset<N>& other) {
int i = 0;
for (; i + 4 < n; i += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
__m128i B = _mm_loadu_si128((__m128i*)(other.data + i));
__m128i C = _mm_or_si128(A, B);
_mm_storeu_si128((__m128i*)(data + i), C);
}
for (; i < n; ++i) {
data[i] |= other.data[i];
}
return *this;
}
inline Bitset<N> operator |(const Bitset<N>& other) const {
Bitset<N> res;
int i = 0;
for (; i + 4 < n; i += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
__m128i B = _mm_loadu_si128((__m128i*)(other.data + i));
__m128i C = _mm_or_si128(A, B);
_mm_storeu_si128((__m128i*)(res.data + i), C);
}
for (; i < n; ++i) {
res.data[i] = data[i] | other.data[i];
}
return res;
}
inline Bitset<N>& operator &=(const Bitset<N>& other) {
int i = 0;
for (; i + 4 < n; i += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
__m128i B = _mm_loadu_si128((__m128i*)(other.data + i));
__m128i C = _mm_and_si128(A, B);
_mm_storeu_si128((__m128i*)(data + i), C);
}
for (; i < n; ++i) {
data[i] &= other.data[i];
}
return *this;
}
inline Bitset<N> operator &(const Bitset<N>& other) const {
Bitset<N> res;
int i = 0;
for (; i + 4 < n; i += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
__m128i B = _mm_loadu_si128((__m128i*)(other.data + i));
__m128i C = _mm_and_si128(A, B);
_mm_storeu_si128((__m128i*)(res.data + i), C);
}
for (; i < n; ++i) {
res.data[i] = data[i] & other.data[i];
}
return res;
}
inline Bitset<N>& operator ^=(const Bitset<N>& other) {
int i = 0;
for (; i + 4 < n; i += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
__m128i B = _mm_loadu_si128((__m128i*)(other.data + i));
__m128i C = _mm_xor_si128(A, B);
_mm_storeu_si128((__m128i*)(data + i), C);
}
for (; i < n; ++i) {
data[i] ^= other.data[i];
}
return *this;
}
inline Bitset<N> operator ^(const Bitset<N>& other) const {
Bitset<N> res;
int i = 0;
for (; i + 4 < n; i += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
__m128i B = _mm_loadu_si128((__m128i*)(other.data + i));
__m128i C = _mm_xor_si128(A, B);
_mm_storeu_si128((__m128i*)(res.data + i), C);
}
for (; i < n; ++i) {
res.data[i] = data[i] ^ other.data[i];
}
return res;
}
inline Bitset<N>& operator <<=(int shift) {
const int full = shift >> 5;
if (full >= n) {
reset();
return *this;
}
if (full) {
memmove(data + full, data, (n - full) * sizeof(unsigned));
memset(data, 0, full * sizeof(unsigned));
}
shift &= 31;
if (shift) {
int i = n - 1;
for (; i >= 4; i -= 4) {
__m128i P = _mm_loadu_si128((__m128i*)(data + i - 4));
__m128i A = _mm_loadu_si128((__m128i*)(data + i - 3));
P = _mm_srli_epi32(P, 32 - shift);
A = _mm_slli_epi32(A, shift);
A = _mm_or_si128(A, P);
_mm_storeu_si128((__m128i*)(data + i - 3), A);
}
for (; i >= 1; --i) {
data[i] = (data[i] << shift) | (data[i - 1] >> (32 - shift));
}
data[0] <<= shift;
}
return *this;
}
inline Bitset<N> operator <<(int shift) const {
Bitset<N> res;
const int full = shift >> 5;
if (full >= n) {
return res;
}
if (full) {
memmove(res.data + full, data, (n - full) * sizeof(unsigned));
memset(res.data, 0, full * sizeof(unsigned));
return res <<= shift & 31;
}
shift &= 31;
if (shift) {
int i = n - 1;
for (; i >= 4; i -= 4) {
__m128i P = _mm_loadu_si128((__m128i*)(data + i - 4));
__m128i A = _mm_loadu_si128((__m128i*)(data + i - 3));
P = _mm_srli_epi32(P, 32 - shift);
A = _mm_slli_epi32(A, shift);
A = _mm_or_si128(A, P);
_mm_storeu_si128((__m128i*)(res.data + i - 3), A);
}
for (; i >= 1; --i) {
res.data[i] = (data[i] << shift) | (data[i - 1] >> (32 - shift));
}
res.data[0] = data[0] << shift;
}
else {
memmove(res.data, data, n * sizeof(unsigned));
}
return res;
}
inline Bitset<N>& operator >>=(int shift) {
const int full = shift >> 5;
if (full >= n) {
reset();
return *this;
}
if (full) {
memmove(data, data + full, (n - full) * sizeof(unsigned));
memset(data + n - full, 0, full * sizeof(unsigned));
}
shift &= 31;
if (shift) {
const unsigned u = (1u << shift) - 1;
int i = 0;
const __m128i U = _mm_set_epi32(u, u, u, u);
for (; i + 4 < n - 1; i += 4) {
__m128i NX = _mm_loadu_si128((__m128i*)(data + i + 1));
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
NX = _mm_and_si128(NX, U);
NX = _mm_slli_epi32(NX, 32 - shift);
A = _mm_srli_epi32(A, shift);
A = _mm_or_si128(A, NX);
_mm_storeu_si128((__m128i*)(data + i), A);
}
for (; i < n - 1; ++i) {
data[i] = (data[i] >> shift) | ((data[i + 1] & u) << (32 - shift));
}
data[n - 1] >>= shift;
}
return *this;
}
inline Bitset<N> operator >>(int shift) const {
Bitset<N> res;
const int full = shift >> 5;
if (full >= n) {
return res;
}
if (full) {
memmove(res.data, data + full, (n - full) * sizeof(unsigned));
memset(res.data + n - full, 0, full * sizeof(unsigned));
return res >>= shift & 31;
}
shift &= 31;
if (shift) {
const unsigned u = (1u << shift) - 1;
int i = 0;
const __m128i U = _mm_set_epi32(u, u, u, u);
for (; i + 4 < n - 1; i += 4) {
__m128i NX = _mm_loadu_si128((__m128i*)(data + i + 1));
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
NX = _mm_and_si128(NX, U);
NX = _mm_slli_epi32(NX, 32 - shift);
A = _mm_srli_epi32(A, shift);
A = _mm_or_si128(A, NX);
_mm_storeu_si128((__m128i*)(res.data + i), A);
}
for (; i < n - 1; ++i) {
res.data[i] = (data[i] >> shift) | ((data[i + 1] & u) << (32 - shift));
}
res.data[n - 1] = data[n - 1] >> shift;
}
else {
memmove(res.data, data, n * sizeof(unsigned));
}
return res;
}
inline int count() const {
return count(0, N);
}
// Counts the number of bits in the range [l..r)
inline int count(int l, int r) const {
if ((l >> 5) == (r >> 5)) {
return _popcnt((data[l >> 5] >> (l & 31)) & ((1u << ((r - l))) - 1));
}
int ans = 0;
if (l & 31) {
ans += _popcnt(data[l >> 5] >> (l & 31));
l += 32 - (l & 31);
}
l >>= 5;
if (r & 31) {
ans += _popcnt(data[r >> 5] & ((1u << (r & 31)) - 1));
r -= r & 31;
}
r >>= 5;
for (; l + 16 < r; l += 16) {
ans += _popcnt(data[l]);
ans += _popcnt(data[l + 1]);
ans += _popcnt(data[l + 2]);
ans += _popcnt(data[l + 3]);
ans += _popcnt(data[l + 4]);
ans += _popcnt(data[l + 5]);
ans += _popcnt(data[l + 6]);
ans += _popcnt(data[l + 7]);
ans += _popcnt(data[l + 8]);
ans += _popcnt(data[l + 9]);
ans += _popcnt(data[l + 10]);
ans += _popcnt(data[l + 11]);
ans += _popcnt(data[l + 12]);
ans += _popcnt(data[l + 13]);
ans += _popcnt(data[l + 14]);
ans += _popcnt(data[l + 15]);
}
for (; l + 8 < r; l += 8) {
ans += _popcnt(data[l]);
ans += _popcnt(data[l + 1]);
ans += _popcnt(data[l + 2]);
ans += _popcnt(data[l + 3]);
ans += _popcnt(data[l + 4]);
ans += _popcnt(data[l + 5]);
ans += _popcnt(data[l + 6]);
ans += _popcnt(data[l + 7]);
}
for (; l + 4 < r; l += 4) {
ans += _popcnt(data[l]);
ans += _popcnt(data[l + 1]);
ans += _popcnt(data[l + 2]);
ans += _popcnt(data[l + 3]);
}
for (; l < r; ++l) {
ans += _popcnt(data[l]);
}
return ans;
}
inline bool none() const {
return none(0, N);
}
inline bool none(int l, int r) const {
if ((l >> 5) == (r >> 5)) {
return ((data[l >> 5] >> (l & 31)) & ((1u << ((r - l))) - 1)) == 0;
}
if (l & 31) {
if (data[l >> 5] >> (l & 31)) return 0;
l += 32 - (l & 31);
}
l >>= 5;
if (r & 31) {
if (data[r >> 5] & ((1u << (r & 31)) - 1)) return 0;
r -= r & 31;
}
r >>= 5;
const __m128i zero = _mm_setzero_si128();
for (; l + 4 < r; l += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + l));
if (_mm_movemask_epi8(_mm_cmpeq_epi32(A, zero)) != 0xffff) return false;
}
for (; l < r; ++l) {
if (data[l]) return false;
}
return true;
}
inline bool any() const {
return !none();
}
inline bool any(int l, int r) const {
return !none(l, r);
}
inline int ctz() const {
return ctz(0, N);
}
inline int ctz(int l, int r) const {
if ((l >> 5) == (r >> 5)) {
int ans = _ctz((data[l >> 5] >> (l & 31)) & ((1u << ((r - l))) - 1));
if (ans > r - l) ans = r - l;
return ans;
}
int ans = 0;
if (l & 31) {
unsigned t = data[l >> 5] >> (l & 31);
if (t) return _ctz(t);
ans += 32 - (l & 31);
l += 32 - (l & 31);
}
l >>= 5;
int rr = r & 31;
r >>= 5;
const __m128i zero = _mm_setzero_si128();
for (; l + 4 < r; l += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + l));
if (_mm_movemask_epi8(_mm_cmpeq_epi32(A, zero)) != 0xffff) {
break;
}
ans += 128;
}
for (; l < r; ++l) {
if (data[l]) {
ans += _ctz(data[l]);
return ans;
}
ans += 32;
}
if (rr) {
int cur = _ctz(data[r] & ((1u << rr) - 1));
if (cur > rr) ans += rr; else
ans += cur;
}
return ans;
}
inline int clz() const {
return clz(0, N);
}
inline int clz(int l, int r) const {
if ((l >> 5) == (r >> 5)) {
int ans = _clz((data[l >> 5] >> (l & 31)) & ((1u << ((r - l))) - 1)) - 32 + r - l;
return ans;
}
int ans = 0;
if (r & 31) {
int t = data[r >> 5] & ((1u << (r & 31)) - 1);
if (t) return _clz(t) - 32 + (r & 31);
ans += r & 31;
r -= r & 31;
}
r >>= 5;
int cl = l & 31;
if (cl) {
l += 32 - cl;
}
l >>= 5;
const __m128i zero = _mm_setzero_si128();
for (; r - 4 >= l; r -= 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + r - 4));
if (_mm_movemask_epi8(_mm_cmpeq_epi32(A, zero)) != 0xffff) {
break;
}
ans += 128;
}
for (; r - 1 >= l; --r) {
if (data[r - 1]) {
ans += _clz(data[r - 1]);
return ans;
}
ans += 32;
}
if (cl) {
int cur = _clz(data[l - 1]);
if (cur > 32 - cl) ans += 32 - cl; else
ans += cur;
}
return ans;
}
inline bool operator ==(const Bitset<N>& other) const {
int i = 0;
for (; i + 4 < n; i += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
__m128i B = _mm_loadu_si128((__m128i*)(other.data + i));
if (_mm_movemask_epi8(_mm_cmpeq_epi32(A, B)) != 0xffff) {
return false;
}
}
for (; i < n; ++i) {
if (data[i] != other.data[i]) {
return false;
}
}
return true;
}
inline bool operator <(const Bitset<N>& other) const {
int i = 0;
for (; i + 4 < n; i += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
__m128i B = _mm_loadu_si128((__m128i*)(other.data + i));
if (_mm_movemask_epi8(_mm_cmpeq_epi32(A, B)) != 0xffff) {
break;
}
}
for (; i < n; ++i) {
if (data[i] != other.data[i]) {
return data[i] < other.data[i];
}
}
return false;
}
inline bool operator >(const Bitset<N>& other) const {
int i = 0;
for (; i + 4 < n; i += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
__m128i B = _mm_loadu_si128((__m128i*)(other.data + i));
if (_mm_movemask_epi8(_mm_cmpeq_epi32(A, B)) != 0xffff) {
break;
}
}
for (; i < n; ++i) {
if (data[i] != other.data[i]) {
return data[i] > other.data[i];
}
}
return false;
}
inline bool operator <=(const Bitset<N>& other) const {
return !operator>(other);
}
inline bool operator >=(const Bitset<N>& other) const {
return !operator<(other);
}
inline bool operator !=(const Bitset<N>& other) const {
return !operator==(other);
}
private:
inline static int _popcnt(unsigned a) {
#ifdef _MSC_VER
return _mm_popcnt_u32(a);
#else
return __builtin_popcount(a);
#endif
}
inline static int _ctz(unsigned a) {
#ifdef _MSC_VER
return _tzcnt_u32(a);
#else
return __builtin_ctz(a);
#endif
}
inline static int _clz(unsigned a) {
#ifdef _MSC_VER
return __lzcnt(a);
#else
return __builtin_clz(a);
#endif
}
const int n = (N + 31) / 32;
unsigned* data;
array<unsigned, (N + 31) / 32> arr_;
};
int a, b, c, d, n, m, k, l, r;
int mas[10002], cool[10002];
Bitset<10002> q;
Bitset<10002> qq[10002], qqq[10002];
int dp[2][10002];
inline void upd(int &a, int b) {
if (a > b) a = b;
}
int main() {
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
scanf("%d%d%d", &n, &l, &r);
rept(i, n) {
scanf("%d", &mas[i]);
}
rept(i, n) {
scanf("%d", &cool[i]);
}
VI crap, nice;
rept(i, n) {
if (!cool[i]) {
crap.pb(mas[i]);
}
else {
nice.pb(mas[i]);
}
}
if (nice.empty()) {
printf("0\n");
exit(0);
}
SORT(crap); SORT(nice);
rept(i, L(crap)) {
q |= q << crap[i];
q.set(crap[i]);
}
m = L(nice);
VI cs = nice;
rep(i, m - 1) {
cs[i] += cs[i - 1];
}
qq[m] = q;
FORD(i, m - 1, 0) {
qq[i] = qq[i + 1] | (qq[i + 1] << nice[i]);
qq[i].set(nice[i]);
qqq[i] = qq[i + 1] | (qqq[i + 1] << nice[i]);
if (i < m - 1) {
qqq[i].set(nice[i]);
}
}
memset(dp, 63, sizeof(dp));
int now = 1, nx = 0;
dp[nx][0] = 0;
int ans = 0;
rept(i, m + 1) {
swap(now, nx);
memset(dp[nx], 63, sizeof(dp[nx]));
a = l;
b = l;
c = l;
while (b <= 10000 && !qq[i].test(b)) ++b;
while (c <= 10000 && !qqq[i].test(c)) ++c;
rept(j, 10001) {
if (dp[now][j] >= INF) continue;
while (j + a >= l) {
if (qq[i].test(a)) {
b = a;
}
if (qqq[i].test(a)) {
c = a;
}
--a;
}
if (b <= 10000) {
int diff = b - l;
int t = i == 0 ? 0 : cs[i - 1];
if (t <= r - l - diff) {
int cur = i - dp[now][j];
ans = max(ans, cur);
}
}
if (c <= 10000) {
int diff = c - l;
int t = i == 0 ? 0 : cs[i - 1];
if (t <= r - l - diff) {
int cur = i - dp[now][j] + 1;
ans = max(ans, cur);
}
}
}
if (i == m) break;
rept(j, 10001) {
if (dp[now][j] >= INF) continue;
// Move to crap
upd(dp[nx][j + nice[i]], dp[now][j] + 1);
// Keep in nice
upd(dp[nx][j], dp[now][j]);
}
}
printf("%d\n", ans);
}
Submission ID: 36599666
-----------------------
#ifdef _MSC_VER
#define _CRT_SECURE_NO_DEPRECATE
#pragma comment(linker, "/STACK:66777216")
#include <cstdio>
#define GETS gets_s
#else
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <stdio.h>
#define GETS gets
#endif
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <iostream>
#include <iterator>
#include <cmath>
#include <cstdlib>
#include <sstream>
#include <fstream>
#include <ctime>
#include <cstring>
#include <functional>
#include <chrono>
#include <intrin.h>
using namespace std;
#define pb push_back
#define ppb pop_back
#define pi 3.1415926535897932384626433832795028841971
#define mp make_pair
#define x first
#define y second
#define pii pair<int,int>
#define pdd pair<double,double>
#define INF 1000000000
#define FOR(i,a,b) for (int _n(b), i(a); i <= _n; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;i--)
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define rep(i,n) FOR(i,1,(n))
#define rept(i,n) FOR(i,0,(n)-1)
#define L(s) (int)((s).size())
#define C(a) memset((a),0,sizeof(a))
#define VI vector <int>
#define ll long long
#include <array>
// SSE2 optimized bitset
template<int N>
class Bitset {
public:
Bitset() : data(arr_.data()) {
reset();
}
Bitset<N>& operator=(const Bitset<N>& other) {
arr_ = other.arr_;
data = arr_.data();
return *this;
}
Bitset<N>(const Bitset<N>& other) {
arr_ = other.arr_;
data = arr_.data();
}
Bitset<N>& operator=(Bitset<N>&& other) {
arr_ = std::move(other.arr_);
data = arr_.data();
return *this;
}
Bitset<N>(Bitset<N>&& other) {
arr_ = std::move(other.arr_);
data = arr_.data();
}
inline void set() {
memset(data, 255, n * sizeof(unsigned));
}
inline void set(int pos) {
data[pos >> 5] |= 1u << (pos & 31);
}
inline void reset() {
memset(data, 0, n * sizeof(unsigned));
}
inline void reset(int pos) {
data[pos >> 5] &= ~(1u << (pos & 31));
}
inline void flip(int pos) {
data[pos >> 5] ^= 1u << (pos & 31);
}
inline bool test(int pos) const {
return (data[pos >> 5] >> (pos & 31)) & 1;
}
inline Bitset<N>& operator |=(const Bitset<N>& other) {
int i = 0;
for (; i + 4 < n; i += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
__m128i B = _mm_loadu_si128((__m128i*)(other.data + i));
__m128i C = _mm_or_si128(A, B);
_mm_storeu_si128((__m128i*)(data + i), C);
}
for (; i < n; ++i) {
data[i] |= other.data[i];
}
return *this;
}
inline Bitset<N> operator |(const Bitset<N>& other) const {
Bitset<N> res;
int i = 0;
for (; i + 4 < n; i += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
__m128i B = _mm_loadu_si128((__m128i*)(other.data + i));
__m128i C = _mm_or_si128(A, B);
_mm_storeu_si128((__m128i*)(res.data + i), C);
}
for (; i < n; ++i) {
res.data[i] = data[i] | other.data[i];
}
return res;
}
inline Bitset<N>& operator &=(const Bitset<N>& other) {
int i = 0;
for (; i + 4 < n; i += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
__m128i B = _mm_loadu_si128((__m128i*)(other.data + i));
__m128i C = _mm_and_si128(A, B);
_mm_storeu_si128((__m128i*)(data + i), C);
}
for (; i < n; ++i) {
data[i] &= other.data[i];
}
return *this;
}
inline Bitset<N> operator &(const Bitset<N>& other) const {
Bitset<N> res;
int i = 0;
for (; i + 4 < n; i += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
__m128i B = _mm_loadu_si128((__m128i*)(other.data + i));
__m128i C = _mm_and_si128(A, B);
_mm_storeu_si128((__m128i*)(res.data + i), C);
}
for (; i < n; ++i) {
res.data[i] = data[i] & other.data[i];
}
return res;
}
inline Bitset<N>& operator ^=(const Bitset<N>& other) {
int i = 0;
for (; i + 4 < n; i += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
__m128i B = _mm_loadu_si128((__m128i*)(other.data + i));
__m128i C = _mm_xor_si128(A, B);
_mm_storeu_si128((__m128i*)(data + i), C);
}
for (; i < n; ++i) {
data[i] ^= other.data[i];
}
return *this;
}
inline Bitset<N> operator ^(const Bitset<N>& other) const {
Bitset<N> res;
int i = 0;
for (; i + 4 < n; i += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
__m128i B = _mm_loadu_si128((__m128i*)(other.data + i));
__m128i C = _mm_xor_si128(A, B);
_mm_storeu_si128((__m128i*)(res.data + i), C);
}
for (; i < n; ++i) {
res.data[i] = data[i] ^ other.data[i];
}
return res;
}
inline Bitset<N>& operator <<=(int shift) {
const int full = shift >> 5;
if (full >= n) {
reset();
return *this;
}
if (full) {
memmove(data + full, data, (n - full) * sizeof(unsigned));
memset(data, 0, full * sizeof(unsigned));
}
shift &= 31;
if (shift) {
int i = n - 1;
for (; i >= 4; i -= 4) {
__m128i P = _mm_loadu_si128((__m128i*)(data + i - 4));
__m128i A = _mm_loadu_si128((__m128i*)(data + i - 3));
P = _mm_srli_epi32(P, 32 - shift);
A = _mm_slli_epi32(A, shift);
A = _mm_or_si128(A, P);
_mm_storeu_si128((__m128i*)(data + i - 3), A);
}
for (; i >= 1; --i) {
data[i] = (data[i] << shift) | (data[i - 1] >> (32 - shift));
}
data[0] <<= shift;
}
return *this;
}
inline Bitset<N> operator <<(int shift) const {
Bitset<N> res;
const int full = shift >> 5;
if (full >= n) {
return res;
}
if (full) {
memmove(res.data + full, data, (n - full) * sizeof(unsigned));
memset(res.data, 0, full * sizeof(unsigned));
return res <<= shift & 31;
}
shift &= 31;
if (shift) {
int i = n - 1;
for (; i >= 4; i -= 4) {
__m128i P = _mm_loadu_si128((__m128i*)(data + i - 4));
__m128i A = _mm_loadu_si128((__m128i*)(data + i - 3));
P = _mm_srli_epi32(P, 32 - shift);
A = _mm_slli_epi32(A, shift);
A = _mm_or_si128(A, P);
_mm_storeu_si128((__m128i*)(res.data + i - 3), A);
}
for (; i >= 1; --i) {
res.data[i] = (data[i] << shift) | (data[i - 1] >> (32 - shift));
}
res.data[0] = data[0] << shift;
}
else {
memmove(res.data, data, n * sizeof(unsigned));
}
return res;
}
inline Bitset<N>& operator >>=(int shift) {
const int full = shift >> 5;
if (full >= n) {
reset();
return *this;
}
if (full) {
memmove(data, data + full, (n - full) * sizeof(unsigned));
memset(data + n - full, 0, full * sizeof(unsigned));
}
shift &= 31;
if (shift) {
const unsigned u = (1u << shift) - 1;
int i = 0;
const __m128i U = _mm_set_epi32(u, u, u, u);
for (; i + 4 < n - 1; i += 4) {
__m128i NX = _mm_loadu_si128((__m128i*)(data + i + 1));
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
NX = _mm_and_si128(NX, U);
NX = _mm_slli_epi32(NX, 32 - shift);
A = _mm_srli_epi32(A, shift);
A = _mm_or_si128(A, NX);
_mm_storeu_si128((__m128i*)(data + i), A);
}
for (; i < n - 1; ++i) {
data[i] = (data[i] >> shift) | ((data[i + 1] & u) << (32 - shift));
}
data[n - 1] >>= shift;
}
return *this;
}
inline Bitset<N> operator >>(int shift) const {
Bitset<N> res;
const int full = shift >> 5;
if (full >= n) {
return res;
}
if (full) {
memmove(res.data, data + full, (n - full) * sizeof(unsigned));
memset(res.data + n - full, 0, full * sizeof(unsigned));
return res >>= shift & 31;
}
shift &= 31;
if (shift) {
const unsigned u = (1u << shift) - 1;
int i = 0;
const __m128i U = _mm_set_epi32(u, u, u, u);
for (; i + 4 < n - 1; i += 4) {
__m128i NX = _mm_loadu_si128((__m128i*)(data + i + 1));
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
NX = _mm_and_si128(NX, U);
NX = _mm_slli_epi32(NX, 32 - shift);
A = _mm_srli_epi32(A, shift);
A = _mm_or_si128(A, NX);
_mm_storeu_si128((__m128i*)(res.data + i), A);
}
for (; i < n - 1; ++i) {
res.data[i] = (data[i] >> shift) | ((data[i + 1] & u) << (32 - shift));
}
res.data[n - 1] = data[n - 1] >> shift;
}
else {
memmove(res.data, data, n * sizeof(unsigned));
}
return res;
}
inline int count() const {
return count(0, N);
}
// Counts the number of bits in the range [l..r)
inline int count(int l, int r) const {
if ((l >> 5) == (r >> 5)) {
return _popcnt((data[l >> 5] >> (l & 31)) & ((1u << ((r - l))) - 1));
}
int ans = 0;
if (l & 31) {
ans += _popcnt(data[l >> 5] >> (l & 31));
l += 32 - (l & 31);
}
l >>= 5;
if (r & 31) {
ans += _popcnt(data[r >> 5] & ((1u << (r & 31)) - 1));
r -= r & 31;
}
r >>= 5;
for (; l + 16 < r; l += 16) {
ans += _popcnt(data[l]);
ans += _popcnt(data[l + 1]);
ans += _popcnt(data[l + 2]);
ans += _popcnt(data[l + 3]);
ans += _popcnt(data[l + 4]);
ans += _popcnt(data[l + 5]);
ans += _popcnt(data[l + 6]);
ans += _popcnt(data[l + 7]);
ans += _popcnt(data[l + 8]);
ans += _popcnt(data[l + 9]);
ans += _popcnt(data[l + 10]);
ans += _popcnt(data[l + 11]);
ans += _popcnt(data[l + 12]);
ans += _popcnt(data[l + 13]);
ans += _popcnt(data[l + 14]);
ans += _popcnt(data[l + 15]);
}
for (; l + 8 < r; l += 8) {
ans += _popcnt(data[l]);
ans += _popcnt(data[l + 1]);
ans += _popcnt(data[l + 2]);
ans += _popcnt(data[l + 3]);
ans += _popcnt(data[l + 4]);
ans += _popcnt(data[l + 5]);
ans += _popcnt(data[l + 6]);
ans += _popcnt(data[l + 7]);
}
for (; l + 4 < r; l += 4) {
ans += _popcnt(data[l]);
ans += _popcnt(data[l + 1]);
ans += _popcnt(data[l + 2]);
ans += _popcnt(data[l + 3]);
}
for (; l < r; ++l) {
ans += _popcnt(data[l]);
}
return ans;
}
inline bool none() const {
return none(0, N);
}
inline bool none(int l, int r) const {
if ((l >> 5) == (r >> 5)) {
return ((data[l >> 5] >> (l & 31)) & ((1u << ((r - l))) - 1)) == 0;
}
if (l & 31) {
if (data[l >> 5] >> (l & 31)) return 0;
l += 32 - (l & 31);
}
l >>= 5;
if (r & 31) {
if (data[r >> 5] & ((1u << (r & 31)) - 1)) return 0;
r -= r & 31;
}
r >>= 5;
const __m128i zero = _mm_setzero_si128();
for (; l + 4 < r; l += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + l));
if (_mm_movemask_epi8(_mm_cmpeq_epi32(A, zero)) != 0xffff) return false;
}
for (; l < r; ++l) {
if (data[l]) return false;
}
return true;
}
inline bool any() const {
return !none();
}
inline bool any(int l, int r) const {
return !none(l, r);
}
inline int ctz() const {
return ctz(0, N);
}
inline int ctz(int l, int r) const {
if ((l >> 5) == (r >> 5)) {
int ans = _ctz((data[l >> 5] >> (l & 31)) & ((1u << ((r - l))) - 1));
if (ans > r - l) ans = r - l;
return ans;
}
int ans = 0;
if (l & 31) {
unsigned t = data[l >> 5] >> (l & 31);
if (t) return _ctz(t);
ans += 32 - (l & 31);
l += 32 - (l & 31);
}
l >>= 5;
int rr = r & 31;
r >>= 5;
const __m128i zero = _mm_setzero_si128();
for (; l + 4 < r; l += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + l));
if (_mm_movemask_epi8(_mm_cmpeq_epi32(A, zero)) != 0xffff) {
break;
}
ans += 128;
}
for (; l < r; ++l) {
if (data[l]) {
ans += _ctz(data[l]);
return ans;
}
ans += 32;
}
if (rr) {
int cur = _ctz(data[r] & ((1u << rr) - 1));
if (cur > rr) ans += rr; else
ans += cur;
}
return ans;
}
inline int clz() const {
return clz(0, N);
}
inline int clz(int l, int r) const {
if ((l >> 5) == (r >> 5)) {
int ans = _clz((data[l >> 5] >> (l & 31)) & ((1u << ((r - l))) - 1)) - 32 + r - l;
return ans;
}
int ans = 0;
if (r & 31) {
int t = data[r >> 5] & ((1u << (r & 31)) - 1);
if (t) return _clz(t) - 32 + (r & 31);
ans += r & 31;
r -= r & 31;
}
r >>= 5;
int cl = l & 31;
if (cl) {
l += 32 - cl;
}
l >>= 5;
const __m128i zero = _mm_setzero_si128();
for (; r - 4 >= l; r -= 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + r - 4));
if (_mm_movemask_epi8(_mm_cmpeq_epi32(A, zero)) != 0xffff) {
break;
}
ans += 128;
}
for (; r - 1 >= l; --r) {
if (data[r - 1]) {
ans += _clz(data[r - 1]);
return ans;
}
ans += 32;
}
if (cl) {
int cur = _clz(data[l - 1]);
if (cur > 32 - cl) ans += 32 - cl; else
ans += cur;
}
return ans;
}
inline bool operator ==(const Bitset<N>& other) const {
int i = 0;
for (; i + 4 < n; i += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
__m128i B = _mm_loadu_si128((__m128i*)(other.data + i));
if (_mm_movemask_epi8(_mm_cmpeq_epi32(A, B)) != 0xffff) {
return false;
}
}
for (; i < n; ++i) {
if (data[i] != other.data[i]) {
return false;
}
}
return true;
}
inline bool operator <(const Bitset<N>& other) const {
int i = 0;
for (; i + 4 < n; i += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
__m128i B = _mm_loadu_si128((__m128i*)(other.data + i));
if (_mm_movemask_epi8(_mm_cmpeq_epi32(A, B)) != 0xffff) {
break;
}
}
for (; i < n; ++i) {
if (data[i] != other.data[i]) {
return data[i] < other.data[i];
}
}
return false;
}
inline bool operator >(const Bitset<N>& other) const {
int i = 0;
for (; i + 4 < n; i += 4) {
__m128i A = _mm_loadu_si128((__m128i*)(data + i));
__m128i B = _mm_loadu_si128((__m128i*)(other.data + i));
if (_mm_movemask_epi8(_mm_cmpeq_epi32(A, B)) != 0xffff) {
break;
}
}
for (; i < n; ++i) {
if (data[i] != other.data[i]) {
return data[i] > other.data[i];
}
}
return false;
}
inline bool operator <=(const Bitset<N>& other) const {
return !operator>(other);
}
inline bool operator >=(const Bitset<N>& other) const {
return !operator<(other);
}
inline bool operator !=(const Bitset<N>& other) const {
return !operator==(other);
}
private:
inline static int _popcnt(unsigned a) {
#ifdef _MSC_VER
return _mm_popcnt_u32(a);
#else
return __builtin_popcount(a);
#endif
}
inline static int _ctz(unsigned a) {
#ifdef _MSC_VER
return _tzcnt_u32(a);
#else
return __builtin_ctz(a);
#endif
}
inline static int _clz(unsigned a) {
#ifdef _MSC_VER
return __lzcnt(a);
#else
return __builtin_clz(a);
#endif
}
const int n = (N + 31) / 32;
unsigned* data;
array<unsigned, (N + 31) / 32> arr_;
};
int a, b, c, d, n, m, k, l, r;
int mas[10002], cool[10002];
Bitset<10002> q;
Bitset<10002> qq[10002], qqq[10002];
int dp[2][10002];
inline void upd(int &a, int b) {
if (a > b) a = b;
}
int main() {
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
scanf("%d%d%d", &n, &l, &r);
rept(i, n) {
scanf("%d", &mas[i]);
}
rept(i, n) {
scanf("%d", &cool[i]);
}
VI crap, nice;
rept(i, n) {
if (!cool[i]) {
crap.pb(mas[i]);
}
else {
nice.pb(mas[i]);
}
}
if (nice.empty()) {
printf("0\n");
exit(0);
}
SORT(crap); SORT(nice);
rept(i, L(crap)) {
q |= q << crap[i];
q.set(crap[i]);
}
m = L(nice);
VI cs = nice;
rep(i, m - 1) {
cs[i] += cs[i - 1];
}
qq[m] = q;
FORD(i, m - 1, 0) {
qq[i] = qq[i + 1] | (qq[i + 1] << nice[i]);
qq[i].set(nice[i]);
qqq[i] = qq[i + 1] | (qqq[i + 1] << nice[i]);
if (i < m - 1) {
qqq[i].set(nice[i]);
}
}
rept(i, m + 1) {
qq[i].set(0);
}
rept(i, m) {
qqq[i].set(0);
}
memset(dp, 63, sizeof(dp));
int now = 1, nx = 0;
dp[nx][0] = 0;
int ans = 0;
rept(i, m + 1) {
swap(now, nx);
memset(dp[nx], 63, sizeof(dp[nx]));
a = l;
b = l;
c = l;
while (b <= 10000 && !qq[i].test(b)) ++b;
while (c <= 10000 && !qqq[i].test(c)) ++c;
rept(j, 10001) {
if (dp[now][j] >= INF) continue;
while (a >= 0 && j + a >= l) {
if (qq[i].test(a)) {
b = a;
}
if (qqq[i].test(a)) {
c = a;
}
--a;
}
if (b <= 10000) {
int diff = b - l;
int t = i == 0 ? 0 : cs[i - 1];
if (t - j <= r - l - diff) {
int cur = i - dp[now][j];
ans = max(ans, cur);
}
}
if (c <= 10000) {
int diff = c - l;
int t = i == 0 ? 0 : cs[i - 1];
if (t - j <= r - l - diff) {
int cur = i - dp[now][j] + 1;
ans = max(ans, cur);
}
}
}
if (i == m) break;
rept(j, 10001) {
if (dp[now][j] >= INF) continue;
// Move to crap
upd(dp[nx][j + nice[i]], dp[now][j] + 1);
// Keep in nice
upd(dp[nx][j], dp[now][j]);
}
}
printf("%d\n", ans);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment