ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#213058 | #584. t3 | Origami_Tobiichi | 100 | 949ms | 8404kb | C++11 | 7.9kb | 2024-11-09 18:38:12 | 2024-11-09 23:02:04 |
answer
#include <bits/stdc++.h>
using namespace std;
namespace Octane
{
// non terrae plus ultra
#define OCTANE
#define BUFFER_SIZE 100000
#define ll long long
#define db double
#define ldb long double
char ibuf[BUFFER_SIZE], obuf[BUFFER_SIZE];
char *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#ifdef ONLINE_JUDGE
#define getchar() ((p1 == p2) and (p2 = (p1 = ibuf) + fread(ibuf, 1, BUFFER_SIZE, stdin), p1 == p2) ? (EOF) : (*p1++))
#define putchar(x) ((p3 == obuf + BUFFER_SIZE) && (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf), *p3++ = x)
#endif // fread in OJ, getchar in local
#define isdigit(ch) (ch > 47 && ch < 58)
#define isspace(ch) (ch < 33 && ch != EOF)
const ll pow10[] = {
(ll)1e0,
(ll)1e1,
(ll)1e2,
(ll)1e3,
(ll)1e4,
(ll)1e5,
(ll)1e6,
(ll)1e7,
(ll)1e8,
(ll)1e9,
(ll)1e10,
(ll)1e11,
(ll)1e12,
(ll)1e13,
(ll)1e14,
(ll)1e15,
(ll)1e16,
(ll)1e17,
(ll)1e18,
};
struct Octane_t
{
~Octane_t()
{
fwrite(obuf, p3 - obuf, 1, stdout);
}
bool flag = false;
operator bool()
{
return flag;
}
} io;
template <typename T>
inline T read()
{
T s = 0;
int w = 1;
char ch;
while (ch = getchar(), !isdigit(ch) && (ch != EOF))
if (ch == '-')
w = -1;
if (ch == EOF)
return 0;
while (isdigit(ch))
s = s * 10 + ch - 48, ch = getchar();
if (ch == '.')
{
ll flt = 0;
int cnt = 0;
while (ch = getchar(), isdigit(ch))
if (cnt < 18)
flt = flt * 10 + ch - 48, cnt++;
s += (db)flt / pow10[cnt];
}
return s *= w;
}
template <typename T>
inline bool read(T &s)
{
s = 0;
int w = 1;
char ch;
while (ch = getchar(), !isdigit(ch) && (ch != EOF))
if (ch == '-')
w = -1;
if (ch == EOF)
return false;
while (isdigit(ch))
s = s * 10 + ch - 48, ch = getchar();
if (ch == '.')
{
ll flt = 0;
int cnt = 0;
while (ch = getchar(), isdigit(ch))
if (cnt < 18)
flt = flt * 10 + ch - 48, cnt++;
s += (db)flt / pow10[cnt];
}
return s *= w, true;
}
inline bool read(char &s)
{
while (s = getchar(), isspace(s))
;
return s != EOF;
}
inline bool read(char *s)
{
char ch;
while (ch = getchar(), isspace(ch))
;
if (ch == EOF)
return false;
while (!isspace(ch))
*s++ = ch, ch = getchar();
*s = '\000';
return true;
}
template <typename T>
void print(T x)
{
static int t[20];
int top = 0;
if (x < 0)
putchar('-'), x = -x;
do
{
t[++top] = x % 10;
x /= 10;
} while (x);
while (top)
putchar(t[top--] + 48);
}
struct empty_type
{
};
int pcs = 8;
empty_type setpcs(int cnt)
{
return pcs = cnt, empty_type();
}
inline void print(empty_type x) {}
inline void print(double x)
{
if (x < 0)
putchar('-'), x = -x;
x += 5.0 / pow10[pcs + 1];
print((ll)(x));
x -= (ll)(x);
if (pcs != 0)
putchar('.');
for (int i = 1; i <= pcs; i++)
x *= 10, putchar((int)x + '0'), x -= (int)x;
}
inline void print(float x)
{
if (x < 0)
putchar('-'), x = -x;
x += 5.0 / pow10[pcs + 1];
print((ll)(x));
x -= (ll)(x);
if (pcs != 0)
putchar('.');
for (int i = 1; i <= pcs; i++)
x *= 10, putchar((int)x + '0'), x -= (int)x;
}
inline void print(char x)
{
putchar(x);
}
inline void print(char *x)
{
for (int i = 0; x[i]; i++)
putchar(x[i]);
}
inline void print(const char *x)
{
for (int i = 0; x[i]; i++)
putchar(x[i]);
}
// support for string
#ifdef _GLIBCXX_STRING
inline bool read(std::string &s)
{
s = "";
char ch;
while (ch = getchar(), isspace(ch))
;
if (ch == EOF)
return false;
while (!isspace(ch))
s += ch, ch = getchar();
return true;
}
inline void print(std::string x)
{
for (string::iterator i = x.begin(); i != x.end(); i++)
putchar(*i);
}
inline bool getline(Octane_t &io, string s)
{
s = "";
char ch = getchar();
if (ch == EOF)
return false;
while (ch != '\n' and ch != EOF)
s += ch, ch = getchar();
return true;
}
#endif
// support for initializer_list
#if __cplusplus >= 201103L
template <typename T, typename... T1>
inline int read(T &a, T1 &...other)
{
return read(a) + read(other...);
}
template <typename T, typename... T1>
inline void print(T a, T1... other)
{
print(a);
print(other...);
}
#endif
// give up iostream
template <typename T>
Octane_t &operator>>(Octane_t &io, T &b)
{
return io.flag = read(b), io;
}
Octane_t &operator>>(Octane_t &io, char *b)
{
return io.flag = read(b), io;
}
template <typename T>
Octane_t &operator<<(Octane_t &io, T b)
{
return print(b), io;
}
#define cout io
#define cin io
#define endl '\n'
#undef ll
#undef db
#undef ldb
#undef BUFFER_SIZE
}
using namespace Octane;
struct node
{
int l, r;
mutable long long val;
node(int L, int R = -1, long long Val = 0)
{
l = L, r = R, val = Val;
}
bool operator<(const node &a) const
{
return l < a.l;
}
};
const int mod = 1e9 + 7;
typedef pair<long long, int> pii;
set<node> odt;
long long a[100005], n, m, seed, vmax;
long long fpow(long long x, long long y, long long mod = 1e9 + 7)
{
long long ans = 1;
x %= mod;
while (y)
{
if (y & 1)
ans = ans * x % mod;
x = x * x % mod;
y >>= 1;
}
return ans;
}
auto split(int pos)
{
auto it = odt.lower_bound(node(pos));
if (it != odt.end() && it->l == pos)
return it;
it--;
int l = it->l, r = it->r;
long long val = it->val;
odt.erase(it);
odt.insert(node(l, pos - 1, val));
return odt.insert(node(pos, r, val)).first;
}
void assign(int l, int r, long long val)
{
auto itr = split(r + 1), itl = split(l);
odt.erase(itl, itr);
odt.insert(node(l, r, val));
}
void add(int l, int r, long long val)
{
auto itr = split(r + 1), itl = split(l);
for (auto it = itl; it != itr; it++)
it->val += val;
}
long long sum(int l, int r, int x)
{
long long ans = 0;
auto itr = split(r + 1), itl = split(l);
for (auto it = itl; it != itr; it++)
ans = (ans + fpow(it->val, x) * ((it->r) - (it->l) + 1)) % mod;
return ans;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
odt.insert(node(i, i, a[i]));
}
for (int i = 1; i <= m; i++)
{
int op, l, r, x;
cin >> op >> l >> r >> x;
if (l > r)
swap(l, r);
if (op == 1)
add(l, r, x);
else if (op == 2)
assign(l, r, x);
else
cout << sum(l, r, x) << endl;
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 2ms
memory: 1228kb
input:
458 823 14431 9895 11970 15308 2575 20181 709 27999 12992 18884 11061 16281 5044 28990 25092 28337 3...
output:
806084096 117884357 581509507 903754571 381316325 789203673 312340523 659242359 741787988 89040104 4...
result:
ok 261 lines
Test #2:
score: 10
Accepted
time: 0ms
memory: 1228kb
input:
481 526 8409 14498 18636 10027 24362 32458 17986 17730 11956 19192 2193 1034 29317 19284 16210 26242...
output:
867105097 717265913 288311190 320452351 133 498037408 473281413 216488030 182572597 611630662 471106...
result:
ok 179 lines
Test #3:
score: 10
Accepted
time: 124ms
memory: 8404kb
input:
100000 100000 15247 4194 9619 4532 22058 2667 21549 16652 25327 12018 13395 11426 7243 11714 22904 2...
output:
54433 544457741 352487648 82525935 532381851 235929450 38218 30045720 19138 459644406 33559 30953524...
result:
ok 33327 lines
Test #4:
score: 10
Accepted
time: 138ms
memory: 8400kb
input:
100000 100000 6264 26207 28424 24165 4852 20798 5803 18679 24588 12238 25786 28622 19900 101 25922 2...
output:
18923 13111195 41716 34447 32091 80654 731180277 9973 523560023 19797 159789457 695071461 3136 95363...
result:
ok 33328 lines
Test #5:
score: 10
Accepted
time: 144ms
memory: 8400kb
input:
100000 100000 15043 9299 7163 25384 24996 3803 24356 12466 22073 12987 8931 14997 3951 32704 23076 8...
output:
754347097 6296 588341566 325967942 180064833 683 831351544 63953 57030 17635 175222109 5280 57193 32...
result:
ok 33349 lines
Test #6:
score: 10
Accepted
time: 145ms
memory: 8400kb
input:
100000 100000 14736 16956 19864 23894 29403 5507 12182 6188 17192 14440 18618 3970 15396 15037 23334...
output:
17008 73008 935797904 16519312 15383 25232 236856418 75334 25854 46510 797344028 517157465 595936107...
result:
ok 33304 lines
Test #7:
score: 10
Accepted
time: 48ms
memory: 4892kb
input:
50000 50000 17799 29763 25337 21321 1391 31852 27418 28753 18524 14044 15976 18893 12274 22834 11348...
output:
19498 473297203 695948777 299749756 50630760 692747746 369627246 181903142 328502296 939823794 69850...
result:
ok 16802 lines
Test #8:
score: 10
Accepted
time: 69ms
memory: 4888kb
input:
50000 50000 10654 14956 14287 25326 8102 30579 11682 23553 272 22672 14460 30241 13026 12738 4912 72...
output:
717018991 140916081 273712387 602991268 878512570 665908548 10388 4939 283493752 435656498 657720400...
result:
ok 16814 lines
Test #9:
score: 10
Accepted
time: 129ms
memory: 7700kb
input:
90000 90000 29538 28214 24706 30393 27759 9002 13458 10243 15713 14881 10630 5593 7942 24578 29370 1...
output:
738835738 738703020 3888 402391875 37270 872563699 273399892 807398793 365897262 255303782 93280847 ...
result:
ok 29904 lines
Test #10:
score: 10
Accepted
time: 150ms
memory: 8404kb
input:
100000 100000 23515 49 31372 25112 16779 21279 30735 32743 14678 15189 1763 23114 32215 14873 20487 ...
output:
576735050 562509678 553431297 662173102 515338212 478400370 879269281 500659410 483381164 1679282 16...
result:
ok 33309 lines