結果
| 問題 |
No.1347 HS Railway
|
| コンテスト | |
| ユーザー |
 8UqsVg4r
|
| 提出日時 | 2021-01-16 00:53:18 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,213 bytes |
| コンパイル時間 | 2,011 ms |
| コンパイル使用メモリ | 186,440 KB |
| 実行使用メモリ | 6,752 KB |
| 最終ジャッジ日時 | 2024-11-26 19:03:50 |
| 合計ジャッジ時間 | 5,257 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 2 |
| other | WA * 50 |
ソースコード
/////////////////////////////////////////////////
///// Give me AC!!!! /////
/////////////////////////////////////////////////
//↑これじゃ気合いが足りない！
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///// お願いしますACをくださいそうじゃないと僕泣きますお願いしますACをくださいJudge様.... /////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define erep(i,N) for(int i = N - 1; i >= 0; i--)
const ll MOD = 1e9+7;
const ll INF = numeric_limits<ll>::max();
const int MAX = 500000;
const ld PI = (acos(-1));
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true;} return false;}
ld rad(ld a) {return a * 180 / PI;}
const int dx[8] = {1, 0, -1, 0, -1, 1, -1, 1};//2次元グリッド上のx軸方向
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};//2次元グリッド上のy軸方向
template<class T> void rm(vector<T> &vec) {
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
}
//using P = pair<int,int>;
struct UnionFind {
vector<int> par;
UnionFind(int n) : par(n, -1) { }
int root(int x) {
if (par[x] < 0) return x;
else return par[x] = root(par[x]);
}
bool same(int x, int y) {
return root(x) == root(y);
}
bool merge(int x, int y) {
x = root(x); y = root(y);
if (x == y) return false;
if (par[x] > par[y]) swap(x, y); // merge technique
par[x] += par[y];
par[y] = x;
return true;
}
int size(int x) {
return -par[root(x)];
}
};
template <typename T> struct BIT {
private:
vector<T> array;
const int n;
public:
BIT(int _n) : array(_n + 1, 0), n(_n) {}
T sum(int i) {
T s = 0;
while (i > 0) {
s += array[i];
i -= i & -i;
}
return s;
}
T sum(int i,int j) {
T ret_i = sum(i - 1);
T ret_j = sum(j);
return ret_j - ret_i;
}
void add(int i,T x) {
while (i <= n) {
array[i] += x;
i += i & -i;
}
}
};
map<ll,ll> factorize_list;
void factorize(ll k) {
while(1){
bool p = true;
for (ll i = 2; i * i <= k; i++){
if (k % i == 0){
factorize_list[i]++;
k /= i;
p = false;
break;
}
}
if(p) {
factorize_list[k]++;
break;
}
}
return ;
}
ll mod(ll val) {
ll res = val % MOD;
if (res < 0) res += MOD;
return res;
}
char upper(char c){
if('a' <= c && c <= 'z'){
c = c - ('a' - 'A');
}
return c;
}
char lower(char c){
if('A' <= c && c <= 'Z'){
c = c + ('a' - 'A');
}
return c;
}
ll fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++){
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
// 二項係数計算
ll COM(int n, int k){
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
ll Expo(ll N,ll K) {
N %= MOD;
if (K == 0) {
return 1;
}
ll Kc = K,rui = N,ans = 1;
while(Kc) {
if (Kc % 2) {
ans *= rui;
ans %= MOD;
}
rui *= rui;
rui %= MOD;
Kc /= 2;
}
return ans;
}
int dp[100050];
ll extGCD(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
ll d = extGCD(b, a%b, y, x); // 再帰的に解く
y -= a / b * x;
return d;
}
// 負の数にも対応した mod (a = -11 とかでも OK)
/*inline ll mod(ll a, ll m) {
return (a % m + m) % m;
}*/
// 逆元計算 (ここでは a と m が互いに素であることが必要)
/*ll modinv(ll a, ll m) {
ll x, y;
extGCD(a, m, x, y);
return mod(x, m); // 気持ち的には x % m だが、x が負かもしれないので
}*/
int op(int a,int b) {
return a ^ b;
}
int e() {
return (int)0;
}
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
public:
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
segtree() : segtree(0) {}
segtree(int n) : segtree(vector<S>(n, e())) {}
segtree(const vector<S>& v) : _n(int(v.size())) {
log = ceil_pow2(_n);
size = 1 << log;
d = vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
template <bool (*f)(S)> int max_right(int l) {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int r) {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
struct edge {
int to;
ll cost;
};
template<class T> T sqroot(T Ex) {
T l = 0,r = min(Ex,(T)(1e9)),unit = 1e-10;//unit:long longのとき1,long doubleのとき精度
if (0.1 != (T)(0.1)) unit = 1;
while (r - l > unit) {
T val = (l + r) / 2;
if (val * val > Ex) r = val;
else l = val;
}
return l;//Ex以下のT型の平方根
}
template<class T> using Graph = vector<vector<T>>;
#define Sugsugar cin.tie(0);ios::sync_with_stdio(false)
template<class T> void sitpress(vector<T> &vec) {
vector<T> array = vec;
rm(array);
for (int i = 0; i < vec.size(); i++) {
int l = -1,r = array.size();
while (r - l > 1) {
int mid = (l + r) / 2;
if (array.at(mid) >= vec.at(i)) r = mid;
else l = mid;
}
vec.at(i) = r;
}
}
int solve(int v) {
int cnt = 0,a = 1;
while (v) {
cnt += (v % 10) * a;
a++;
v /= 10;
}
return cnt;
}
signed main() {
Sugsugar;
int N;
cin >> N;
vector<vector<ll>> A(5);
vector<pair<int,int>> sec(5);
for (int i = 0; i < 5; i++) {
int l,r;
cin >> l >> r;
sec.at(i) = {l,r};
for (int j = l; j < r; j++) {
ll a;
cin >> a;
A.at(i).push_back(a);
}
}
int M;
cin >> M;
vector<vector<ll>> train(5);
for (int i = 0; i < M; i++) {
int B;
ll S;
cin >> B >> S;
B--;
train.at(B).push_back(S);
}
for (int i = 0; i < 5; i++) sort(train.at(i).begin(),train.at(i).end());
ll ans = 0;
for (int i = 0; i < 4; i++) {
for (int j = i + 1; j < 5; j++) {
int l = max(sec.at(i).first,sec.at(j).first),r = min(sec.at(i).second,sec.at(j).second);
if (l > r) continue;
ll p = 0,q = 0;
for (int k = sec.at(i).first; k < l; k++) p += A.at(i).at(k - sec.at(i).first);
for (int k = sec.at(j).first; k < l; k++) q += A.at(j).at(k - sec.at(j).first);
cout << p << ' ' << q << endl;
ll c = 0,d = 0;
for (int k = l; k < r; k++) {
c += A.at(i).at(k - sec.at(i).first);
d += A.at(j).at(k - sec.at(j).first);
}
for (int k = 0; k < train.at(i).size(); k++) {
ll E = train.at(i).at(k);
ll s = upper_bound(train.at(j).begin(),train.at(j).end(),E + p - q) - train.at(j).begin();
ll f = lower_bound(train.at(j).begin(),train.at(j).end(),E + p + c - q - d) - train.at(j).begin();
//cout << s << ' ' << f << endl;
ans += s - f;
}
}
}
cout << ans << endl;
return 0;
}