ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#212995 | #3843. A | shiruiheng | 20 | 708ms | 14036kb | C++11 | 3.2kb | 2024-10-27 11:24:00 | 2024-10-27 13:03:41 |
answer
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define pi pair<ll, ll>
#define se second
#define mod 1000000007ll
#define N 111111
/*
struct h{
ll t, x, y, bh;
void read(int k, int i){
t = k;
bh = i;
scanf("%lld%lld", &x, &y);
}
bool operator<(const h &r)const{
return x != r.x ? x < r.x : y > r.y;
}
}q[4][N];
//*/
struct frac
{
ll a, b, c;
void init()
{
ll g = __gcd(b, c);
b /= g, c /= g;
}
} res[N];
ll y[N];
ll n, k, m, tot[4], op[N], x[N], a[N], b[N], qu[N], nxt[N], cnt;
ll ans[N] = {1};
// priority_queue<ld> q;
ll bigmul(ll a, ll b, ll m)
{
unsigned long long c =
(unsigned long long)a * b -
(unsigned long long)((long double)a / m * b + 0.5L) * m;
return (c + m) % m;
}
ll qpow(ll x, ll y)
{
ll ans = 1, res = x % mod;
while (y)
{
if (y & 1)
ans = bigmul(ans, res, mod);
res = bigmul(res, res, mod);
y >>= 1;
}
return ans;
}
ll inv(ll x)
{
return qpow(x, mod - 2);
}
priority_queue<pair<ld, ll>> q;
void print(ll *a, ll cnt)
{
if (!cnt)
return;
printf("%lld%c", *a, " \n"[!cnt]);
print(a + 1, cnt - 1);
}
signed main()
{
scanf("%lld%lld", &n, &m);
op[0] = 3;
y[0] = 1;
for (int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
b[i] = a[i];
ans[0] *= a[i];
ans[0] %= mod;
q.push({1.0, 0});
}
for (int i = 1; i <= m; i++)
{
scanf("%lld%lld%lld", &op[i], &x[i], &y[i]);
// q[op][++tot[op]].read(op, i);
++tot[op[i]];
if (op[i] == 1)
{
if(qu[x[i]] < y[i])
qu[x[i]] = y[i], nxt[x[i]] = i;
// qu[N] = max(qu[N], q[1][tot[op]].y - a[i]);
}
else if (op[i] == 2)
{
q.push({1.0 * (y[i] + a[x[i]]) / a[x[i]], i});
}
else
{
q.push({y[i], i});
cnt++;
}
}
// sort(q[1] + 1, q[1] + 1 + tot[1]);
for (int i = 1; i <= n; i++)
{
if (qu[i] > a[i]){
q.push({1.0 * (qu[i]) / a[i], nxt[i]});
//cerr << i << " " << nxt[i] << " moo\n";
}
}
/*
if(!tot[2]){
for(int i = 1 ; i <= m ; i++){
}
return 0;
}
if((m - cnt) * m <= 20000000){
ll prod = 1, tmp;
for(int i = 1 ; i <= m ; i++){
tmp = 1;
int bh = q.top().se;
ans[i] = tmp * prod % mod;
}
print(ans, m + 1);
return 0;
}
//*/
for (int i = 1; i <= m; i++)
{
int bh = q.top().se;
ll res = 0;
if(op[bh] == 1){
res = (y[bh] - b[x[bh]] + a[x[bh]]) * inv(a[x[bh]]) % mod;
a[x[bh]] += y[bh] - b[x[bh]];
}
else if(op[bh] == 2){
res = (y[bh] + a[x[bh]]) * inv(a[x[bh]]) % mod;
a[x[bh]] += y[bh];
}
else{
res = y[bh];
}
ans[i] = res * ans[i - 1] % mod;
//cerr << res << " \n"[i == m];
q.pop();
}
print(ans, m + 1);
exit(0);
}
/*
2 4
13 20
1 1 14
1 2 30
2 1 6
3 2 2
*/
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 1ms
memory: 1264kb
input:
10 9 499300 506104 170546 92835 547291 820903 786266 716186 780754 350410 1 2 860226 1 7 262313 3 2 ...
output:
949916237 273355785 109253490 342937847 165967338 193680399 668838116 449049268 449049268 449049268
result:
ok single line: '949916237 273355785 109253490 ... 449049268 449049268 449049268 '
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 1420kb
input:
838 995 328218 190018 869417 956360 920685 135786 504711 888313 754830 943461 140489 119510 975517 4...
output:
977624914 525643123 863628113 707859516 862306123 812596096 414661171 658774701 128812101 977258179 ...
result:
wrong answer 1st lines differ - expected: '977624914 525643123 863628113 ...9 965384179 965384179 96...
Test #3:
score: 0
Wrong Answer
time: 0ms
memory: 1404kb
input:
804 888 919099 183209 297149 271173 193797 566221 659181 386055 601753 715300 283689 725899 231064 6...
output:
758231827 982285455 982778357 196498191 711800559 396455055 816629270 114093684 921483452 511283414 ...
result:
wrong answer 1st lines differ - expected: '758231827 982285455 982778357 ...9 552291189 552291189 55...
Test #4:
score: 0
Wrong Answer
time: 90ms
memory: 11792kb
input:
97225 82672 856890 901880 920790 122917 605005 736241 523875 983819 184041 849540 673700 554037 2496...
output:
712254946 91994452 807394885 702209394 296867686 75227322 250105192 428152388 291173890 238269117 56...
result:
wrong answer 1st lines differ - expected: '712254946 91994452 807394885 7...8 533932838 134692828 33...
Test #5:
score: 10
Accepted
time: 75ms
memory: 13932kb
input:
97375 83905 532589 835657 855226 579469 192565 620993 89287 812372 705900 934429 954068 305807 40876...
output:
956516857 241652731 687990203 806517336 228519943 374605637 545265036 777270125 92719263 758322272 4...
result:
ok single line: '956516857 241652731 687990203 ... 129176681 129176681 129176681 '
Test #6:
score: 0
Wrong Answer
time: 100ms
memory: 14036kb
input:
84403 89476 657027 571610 109219 331267 561010 208384 689180 992889 316802 852315 660936 390331 9340...
output:
540397934 434494535 544195130 3774864 761070203 979447148 691908017 115026552 679150793 973720729 31...
result:
wrong answer 1st lines differ - expected: '540397934 434494535 544195130 ...2 836027822 836027822 83...
Test #7:
score: 0
Wrong Answer
time: 94ms
memory: 13676kb
input:
96606 92331 870095 773626 804775 42308 917827 100693 6651 387580 44282 208204 137017 390782 688022 6...
output:
322460451 934296501 101619151 179890569 108095167 952447253 89752879 901634873 490942353 994397338 7...
result:
wrong answer 1st lines differ - expected: '322460451 934296501 101619151 ...1 252960641 252960641 25...
Test #8:
score: 0
Wrong Answer
time: 137ms
memory: 13800kb
input:
80440 84759 541342 971256 801890 950405 604598 46057 371679 452853 615046 760451 709735 956995 97307...
output:
821708799 219577694 665976802 490219867 548178015 542345954 935489718 646217068 490791568 548097544 ...
result:
wrong answer 1st lines differ - expected: '821708799 219577694 665976802 ...0 862590660 862590660 86...
Test #9:
score: 0
Wrong Answer
time: 124ms
memory: 13664kb
input:
97638 97412 359189 691954 775011 161646 327465 718513 685644 837780 525594 401038 167837 283051 1197...
output:
823078265 497690641 236818754 674585904 606991860 418192592 912747908 540693829 844215937 893047230 ...
result:
wrong answer 1st lines differ - expected: '823078265 497690641 236818754 ...4 270309474 270309474 27...
Test #10:
score: 0
Wrong Answer
time: 87ms
memory: 13788kb
input:
82250 86515 922214 64589 463852 364145 291234 758178 442834 607900 509378 889490 108840 488390 24542...
output:
934768286 475151787 411513524 325010113 983854452 884116216 717223578 475318220 379978723 30235191 8...
result:
wrong answer 1st lines differ - expected: '934768286 475151787 411513524 ...5 874338965 874338965 87...