QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #133581 | #4940. Token Distance | Delay_for_five_minutes# | WA | 106ms | 19288kb | C++14 | 4.6kb | 2023-08-02 11:29:58 | 2023-08-02 11:30:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n , q;
typedef long long ll;
const int mod = 1e9 + 7;
int a[100005];
template<int K>
struct Seg {
int sum[100005 * 4][K + 1];
int mn[100005 * 4] , mx[100005 * 4];
int pos[100005];
int c[K + 1][K + 1];
int pre[100005][K + 1];
int fp(int a,int b) {
int ans = 1;
while(b) {
ans = 1LL*ans*a%mod;b--;
}
return ans;
}
void init () {
c[0][0] = 1;
memset(pre,0,sizeof(pre));
for(int i = 1;i <= K;i++) {
c[i][0] = 1;
for(int j = 1;j <= i;j++) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
for(int i = 1;i <= n;i++) {
for(int j = 0;j <= K;j++) pre[i][j] = (pre[i - 1][j] + fp(i , j)) % mod;
}
}
void rec(int u) {
for(int i = 0;i <= K;i++) sum[u][i] = (sum[u<<1][i] + sum[u<<1|1][i]) % mod;
mn[u] = min(mn[u << 1 | 1] , mn[u << 1]);
mx[u] = max(mx[u << 1] , mx[u << 1 | 1]);
}
void build(int u,int l,int r) {
if(l == r) {
sum[u][0] = 1; pos[l] = u;
mn[u] = mx[u] = a[l];
for(int i = 1;i <= K;i++) sum[u][i] = 1LL*sum[u][i - 1]*a[l]% mod;
return;
}
build(u<<1 , l , (l + r >> 1));
build(u<<1|1 , (l + r >> 1) + 1 , r);
rec(u);
}
pair<int,int> qdif(int u,int l,int r,int ql,int qr) {
if(ql <= l && qr >= r) {
return pair<int,int>{mn[u] , mx[u]};
}
pair<int,int> ans = pair<int,int>{1e9 , 0};
int md = (l + r >> 1);
if(ql <= md) ans = qdif(u<<1 , l , md , ql , qr);
if(qr > md) {
auto d = qdif(u<<1|1 , md + 1 , r , ql , qr);
ans.first = min(ans.first , d.first);
ans.second = max(ans.second , d.second);
}
//printf("u %d , %d %d , %d %d\n",u,l,r,ans.first,ans.second);
return ans;
}
array<int,K > query(int u,int l,int r,int ql,int qr) {
if(ql <= l && qr >= r) {
array<int,K> ans;
for(int i = 1;i <= K;i++) ans[i - 1] = sum[u][i];
// printf("Q %d %d , %d %d , %d\n",l,r,ql,qr,ans[0]);
return ans;
}
array<int,K> ans;
for(int i = 0;i < K;i++) ans[i] = 0;
int md = (l + r >> 1);
if(ql <= md) ans = query(u<<1 , l , md , ql , qr);
if(qr > md) {
auto d = query(u<<1|1 , md + 1 , r , ql , qr);
for(int i = 0;i < K;i++) ans[i] = (ans[i] + d[i]) % mod;
}
// printf("Q %d %d , %d %d , %d\n",l,r,ql,qr,ans[0]);
return ans;
}
void upd(int p)
{
int u = pos[p]; mn[u] = mx[u] = a[p];
for(int i = 1;i <= K;i++) sum[u][i] = 1LL*sum[u][i - 1] * a[p] % mod;
u >>= 1;
while(u) {
rec(u) ;
u >>= 1;
}
}
int get(int a1,int d,int len,int k) {
int ans = 0;
for(int j = 0;j <= k;j++) {
int u = 1LL*c[k][j]*fp(a1 , k - j) % mod * fp(d , j) % mod;
ans = (ans + 1LL*u*pre[len][j]) % mod;
}
// printf("%d %d %d , %d\n",a1,d,len,ans);
return ans;
}
};
Seg<5> seg;
const int K = 5;
int main()
{
// freopen("in.txt","r",stdin);
ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0);
cin >> n >> q;
for(int i =1 ;i <= n;i++) {cin >> a[i]; a[i]++;}
seg.init();
seg.build(1 ,1 , n);
while(q--) {
int op;cin >> op;
if(op == 1) {
int x , y;cin >> x >> y; y++;
a[x] = y;
seg.upd(x);
}
else {
int l , r;cin >> l >> r;
if(r - l + 1 <= 2) {
cout << "YES\n" ; continue;
}
int len = r- l + 1;
pair<int,int> d = seg.qdif(1 , 1 , n , l , r);
int dif = d.second - d.first ;
if(dif % (len - 1) != 0) {
cout << "NO\n" ; continue;
}
dif /= (len - 1);
// printf("A1 %d dif %d\n",d.first - dif , dif);
array<int,K> ar = seg.query(1 , 1 , n , l , r) ;
// printf("%d %d %d\n",ar[0],ar[1],ar[2]);
// printf("%d %d %d\n",seg.get(-2 , 3 , 4 , 1) , seg.get(-2 , 3 , 4 , 2) , seg.get(-2 , 3 , 4 , 3)) ;
bool ff = 1;
for(int j = 0;j < K;j++) {
if(ar[j] != seg.get(d.first - dif , dif , len , j + 1)) {
ff = 0;break;
}
}
if(ff) cout << "YES\n";
else cout << "NO\n";
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 10944kb
input:
5 7 1 1 1 10 1 2 1 3 2 1 5 1 5 4 1 3 7 2 2 4 2 2 5 2 4 5
output:
YES NO NO YES YES
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 10956kb
input:
2 1 0 1000000000 2 1 2
output:
YES
result:
ok single line: 'YES'
Test #3:
score: 0
Accepted
time: 18ms
memory: 19072kb
input:
81473 13549 972586683 972586964 972587245 972587526 972587807 972588088 972588369 972588650 972588931 972589212 972589493 972589774 972590055 972590336 972590617 972590898 972591179 972591460 972591741 972592022 972592303 972592584 972592865 972593146 972593427 972593708 972593989 972594270 97259455...
output:
YES YES YES YES NO YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES NO YES NO YES YES YES NO YES YES YES YES YES NO YES NO YES YES YES YES YES NO YES NO YES NO YES YES YES YES YES NO YES NO YES NO YES NO YES YES YES YES YES YES YES YES YES NO YES NO YES NO YES YES YES YES Y...
result:
ok 4517 lines
Test #4:
score: 0
Accepted
time: 10ms
memory: 19164kb
input:
81473 13549 994993061 993089286 973546017 983608065 980300695 994305454 992559601 974765838 987574661 988923180 987601637 991357764 981678157 994388630 987066613 976087381 985770922 989296067 975698758 977548300 992236732 978102432 983875296 979745439 977111907 992622264 988921213 987697458 99145442...
output:
NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES...
result:
ok 4517 lines
Test #5:
score: 0
Accepted
time: 13ms
memory: 17000kb
input:
81473 13549 972586964 972586683 972587526 972587245 972588088 972587807 972588650 972588369 972589212 972588931 972589774 972589493 972590336 972590055 972590898 972590617 972591460 972591179 972592022 972591741 972592584 972592303 972593146 972592865 972593708 972593427 972594270 972593989 97259483...
output:
NO NO YES YES NO NO YES NO NO YES NO YES NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO YES YES NO NO NO YES NO NO NO YES NO YES NO YES NO NO NO NO NO NO NO YES NO YES NO NO YES NO NO YES NO NO NO NO NO NO YES YES NO NO NO NO YES NO NO NO NO NO NO YES...
result:
ok 13549 lines
Test #6:
score: 0
Accepted
time: 19ms
memory: 17020kb
input:
81473 13549 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 13635105...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES ...
result:
ok 13549 lines
Test #7:
score: 0
Accepted
time: 17ms
memory: 17168kb
input:
81473 13549 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 136351051 13635105...
output:
YES NO YES NO YES YES NO YES NO YES YES YES NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO YES NO NO NO YES NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO YES NO NO NO NO YES NO NO NO NO NO...
result:
ok 6727 lines
Test #8:
score: 0
Accepted
time: 106ms
memory: 19104kb
input:
96888 91338 0 10321 20642 30963 41284 51605 61926 72247 82568 92889 103210 113531 123852 134173 144494 154815 165136 175457 185778 196099 206420 216741 227062 237383 247704 258025 268346 278667 288988 299309 309630 319951 330272 340593 350914 361235 371556 381877 392198 402519 412840 423161 433482 4...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES ...
result:
ok 91338 lines
Test #9:
score: 0
Accepted
time: 84ms
memory: 17232kb
input:
96888 91338 0 10321 20642 30963 41284 51605 61926 72247 82568 92889 103210 113531 123852 134173 144494 154815 165136 175457 185778 196099 206420 216741 227062 237383 247704 258025 268346 278667 288988 299309 309630 319951 330272 340593 350914 361235 371556 381877 392198 402519 412840 423161 433482 4...
output:
NO YES YES NO NO YES YES NO YES YES YES YES YES NO YES NO YES NO NO NO YES YES YES NO NO YES YES NO YES NO YES YES NO NO YES YES NO NO NO NO YES YES NO YES YES NO YES NO YES YES YES NO YES YES NO NO YES YES YES NO NO NO NO YES NO YES YES YES YES NO YES NO YES YES NO YES NO YES YES YES YES YES YES YE...
result:
ok 91338 lines
Test #10:
score: 0
Accepted
time: 47ms
memory: 19064kb
input:
96888 91338 0 10321 20642 30963 41284 51605 61926 72247 82568 92889 103210 113531 123852 134173 144494 154815 165136 175457 185778 196099 206420 216741 227062 237383 247704 258025 268346 278667 288988 299309 309630 319951 330272 340593 350914 361235 371556 381877 392198 402519 412840 423161 433482 4...
output:
YES YES NO NO NO NO YES NO YES YES NO NO YES NO NO NO NO YES NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 45670 lines
Test #11:
score: 0
Accepted
time: 43ms
memory: 17012kb
input:
96888 91338 148622400 313851289 796564459 844340368 558593162 622118917 828177682 162586713 809187042 120384144 635536217 253999810 681392420 868894027 212922230 762102640 996956995 352833706 345175524 294127858 22179829 707700649 122520591 837858780 906906270 596853109 3416251 593901303 130684502 8...
output:
NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES...
result:
ok 45670 lines
Test #12:
score: 0
Accepted
time: 71ms
memory: 17232kb
input:
96888 91338 0 10321 20642 30963 41284 51605 61926 72247 82568 92889 103210 113531 123852 134173 144494 154815 165136 175457 185778 196099 206420 216741 227062 237383 247704 258025 268346 278667 288988 299309 309630 319951 330272 340593 350914 361235 371556 381877 392198 402519 412840 423161 433482 4...
output:
YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES NO YES YES YES YES YES YES YES YES YES NO YES NO YES NO YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES NO YES YES YES NO YES YES YES YES YES YES YES YES YE...
result:
ok 45670 lines
Test #13:
score: 0
Accepted
time: 22ms
memory: 18964kb
input:
81473 13549 972586683 972586964 972587245 972587526 972587807 972588088 972588369 972588650 972588931 972589212 972589493 972589774 972590055 972590336 972590617 972590898 972591179 972591460 972591741 972592022 972592303 972592584 972592865 972593146 972593427 972593708 972593989 972594270 97259455...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES ...
result:
ok 13549 lines
Test #14:
score: 0
Accepted
time: 27ms
memory: 17084kb
input:
96888 91338 595841651 917330480 207421137 35297820 388823033 754743767 175477642 575292540 427299721 685520820 420849096 990712790 335515068 880143917 298720703 665301981 644711586 983560337 804026542 699918615 863609675 666912057 857974409 277769073 133161542 363784287 536671358 866138320 98617155 ...
output:
NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES...
result:
ok 45670 lines
Test #15:
score: 0
Accepted
time: 61ms
memory: 17028kb
input:
96888 91338 0 10321 20642 30963 41284 51605 61926 72247 82568 92889 103210 113531 123852 134173 144494 154815 165136 175457 185778 196099 206420 216741 227062 237383 247704 258025 268346 278667 288988 299309 309630 319951 330272 340593 350914 361235 371556 381877 392198 402519 412840 423161 433482 4...
output:
NO YES NO YES YES YES YES YES YES YES NO YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES NO YES NO YES YES YES NO YES NO YES NO YES YES YES YES YES NO YES NO YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YE...
result:
ok 30446 lines
Test #16:
score: 0
Accepted
time: 39ms
memory: 19288kb
input:
96888 91338 509186535 219424460 517598150 635835526 539550917 500630426 813821171 353246546 400661220 590412805 346537896 453484098 10991865 684901560 100299478 958469986 846580025 936042453 885531479 332171064 822779799 75591004 655115154 686367142 992002915 202559946 242419648 534978714 132769344 ...
output:
NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES...
result:
ok 30446 lines
Test #17:
score: 0
Accepted
time: 67ms
memory: 17076kb
input:
96888 91338 0 10321 20642 30963 41284 51605 61926 72247 82568 92889 103210 113531 123852 134173 144494 154815 165136 175457 185778 196099 206420 216741 227062 237383 247704 258025 268346 278667 288988 299309 309630 319951 330272 340593 350914 361235 371556 381877 392198 402519 412840 423161 433482 4...
output:
YES YES NO YES NO YES YES YES YES YES YES YES NO YES YES YES YES YES NO YES YES YES NO YES YES YES YES YES YES YES YES YES NO YES YES YES NO YES YES YES YES YES NO YES YES YES NO YES YES YES NO YES YES YES NO YES YES YES YES YES NO YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES NO YES YE...
result:
ok 30446 lines
Test #18:
score: 0
Accepted
time: 41ms
memory: 17028kb
input:
96888 91338 17814046 703974768 403530458 305635773 465157149 240293522 124729285 319641370 532161081 262070832 362535446 68201168 249148940 223748959 999753986 125544644 20218839 382723322 5274031 883343427 539984399 956044551 312623090 985985772 831181093 265538688 200082906 7720108 941636435 45280...
output:
NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES...
result:
ok 30446 lines
Test #19:
score: 0
Accepted
time: 51ms
memory: 17068kb
input:
96888 91338 10321 0 30963 20642 51605 41284 72247 61926 92889 82568 113531 103210 134173 123852 154815 144494 175457 165136 196099 185778 216741 206420 237383 227062 258025 247704 278667 268346 299309 288988 319951 309630 340593 330272 361235 350914 381877 371556 402519 392198 423161 412840 443803 4...
output:
YES YES YES NO YES NO NO NO NO YES NO NO NO NO NO NO YES NO YES NO NO NO YES NO NO YES YES NO NO NO NO NO NO NO NO YES NO NO NO YES YES NO YES YES NO NO NO NO NO NO YES NO YES YES YES NO YES YES YES NO NO NO NO NO NO YES NO NO NO NO NO NO NO YES NO NO YES YES NO NO NO NO NO NO NO NO NO NO YES YES NO...
result:
ok 91338 lines
Test #20:
score: -100
Wrong Answer
time: 39ms
memory: 17020kb
input:
96888 91338 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 10...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
wrong answer 1st lines differ - expected: 'YES', found: 'NO'