QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#749461#7475. NOIP2016 人生巅峰I_be_wanna100 ✓161ms4748kbC++201.3kb2024-11-15 01:02:272024-11-15 01:02:27

Judging History

你现在查看的是最新测评结果

  • [2024-11-15 01:02:27]
  • 评测
  • 测评结果:100
  • 用时:161ms
  • 内存:4748kb
  • [2024-11-15 01:02:27]
  • 提交

answer

#include<bits/stdc++.h>
#define N 100050
#define M 13005
#define lowbit(x) (x & -x)
using namespace std;
int t[N], n;
void update(int x, int y) {
    for(; x <= n; x += lowbit(x)) t[x] += y;
}
int query(int x) {
    int ret = 0;
    for(; x; x -= lowbit(x)) ret += t[x];
    return ret;
}
int m, mod, a[N], f[M][20];
bitset<M> S;
int main() {
    scanf("%d%d%d", &n, &m, &mod);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    for(int i = 0; i < mod; i ++) f[i][0] = 1ll * i * i * i % mod;
    for(int j = 1; j <= 18; j ++)
        for(int i = 1; i < mod; i ++)
            f[i][j] = f[f[i][j - 1]][j - 1];
    
    while(m --) {
        int o, l, r;
        scanf("%d%d%d", &o, &l, &r);
        if(o == 2) update(l, 1), update(r + 1, -1);
        else {
            if(r - l + 1 > 13) printf("Yuno\n");
            else {
                int ff = 0; S.reset(); S[0] = 1;
                for(int i = l; i <= r; i ++) {
                    int x = a[i], tg = query(i);
                    for(int j = 18; j >= 0; j --) if((tg >> j) & 1) x = f[x][j];
                    x ++;
                    if((S & (S << x)).any()) {ff = 1; break;}
                    S |= (S << x);
                }
                if(ff) printf("Yuno\n");
                else printf("Yuki\n");
            }
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 153ms
memory: 4612kb

input:

100000 100000 233
179 131 37 218 152 124 73 211 220 161 103 24 5 47 106 9 201 30 60 132 126 225 174 160 107 1 32 6 125 159 157 226 44 137 91 31 56 151 169 153 86 126 218 15 15 228 26 168 82 221 198 148 8 206 208 7 225 168 83 50 206 199 180 219 63 44 210 190 182 168 176 179 3 121 48 210 176 210 122 1...

output:

Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuki
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuno
Yuki
Yuki
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuki
...

result:

ok 50158 lines

Test #2:

score: 10
Accepted
time: 161ms
memory: 4656kb

input:

100000 100000 1000
578 341 696 928 250 97 924 913 609 894 250 765 824 779 868 902 613 690 496 372 455 702 153 980 118 971 218 647 283 528 157 309 136 29 164 701 918 596 330 947 470 285 775 67 203 265 961 532 111 93 211 18 656 753 262 30 544 823 878 383 430 677 743 11 156 451 862 464 168 97 496 409 7...

output:

Yuki
Yuno
Yuno
Yuki
Yuki
Yuki
Yuki
Yuki
Yuki
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuki
Yuki
Yuno
Yuki
Yuki
Yuki
Yuki
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuki
Yuno
Yuki
Yuno
Yuki
Yuno
Yuki
Yuno
Yuki
Yuki
Yuno
Yuki
Yuno
Yuki
Yuno
Yuno
Yuno
Yuki
Yuno
Yuki
Yuno
Yuki
Yuki
Yuki
Yuki
Yuno
Yuno
...

result:

ok 50094 lines

Test #3:

score: 10
Accepted
time: 128ms
memory: 4648kb

input:

100000 100000 666
314 54 210 486 159 61 533 641 607 49 538 538 542 236 466 615 656 540 2 16 212 338 528 31 68 113 430 219 557 248 189 13 419 304 505 19 137 584 192 494 611 523 165 615 534 535 542 285 477 425 88 306 9 450 46 502 231 52 255 56 278 181 496 199 525 322 628 593 494 316 367 482 300 522 45...

output:

Yuno
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuki
Yuno
Yuki
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuki
Yuno
Yuki
Yuki
Yuki
Yuno
Yuki
Yuno
Yuki
Yuno
Yuno
Yuno
Yuki
Yuki
Yuno
Yuki
Yuno
...

result:

ok 50062 lines

Test #4:

score: 10
Accepted
time: 161ms
memory: 4660kb

input:

100000 100000 1000
712 56 243 687 161 51 460 977 445 178 179 573 5 41 235 858 24 463 228 625 748 840 162 660 224 624 121 10 993 133 916 161 267 941 208 147 686 473 453 617 234 403 791 87 376 902 989 394 788 968 176 390 387 637 697 890 582 718 400 103 881 281 94 569 178 504 282 437 627 326 732 887 46...

output:

Yuki
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuki
Yuki
Yuno
Yuno
Yuno
Yuki
Yuki
Yuno
Yuki
Yuki
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuki
Yuno
Yuno
Yuki
Yuki
Yuno
Yuki
Yuki
Yuki
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuki
Yuki
Yuno
Yuno
Yuki
Yuki
Yuki
Yuki
Yuno
...

result:

ok 50295 lines

Test #5:

score: 10
Accepted
time: 155ms
memory: 4684kb

input:

100000 100000 233
205 166 222 61 140 162 149 225 80 217 80 145 52 185 59 218 41 120 90 73 162 193 125 21 66 200 108 44 149 95 213 144 141 178 131 163 206 161 89 105 179 107 192 126 154 227 206 63 13 182 176 221 163 178 25 175 207 222 186 223 167 181 148 105 183 20 92 135 15 167 79 120 171 15 207 114...

output:

Yuno
Yuki
Yuno
Yuki
Yuno
Yuki
Yuno
Yuki
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuki
Yuki
Yuno
Yuki
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
...

result:

ok 50021 lines

Test #6:

score: 10
Accepted
time: 158ms
memory: 4608kb

input:

100000 100000 1000
679 866 426 220 115 544 105 479 168 118 660 132 1 416 697 308 782 30 703 748 881 880 66 46 52 129 428 92 367 882 876 188 20 899 733 404 109 727 218 659 535 910 563 696 548 259 465 23 443 648 619 7 155 734 449 777 870 36 576 147 567 3 920 965 227 872 200 960 832 587 313 268 684 948...

output:

Yuno
Yuki
Yuki
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuki
Yuno
Yuki
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuki
Yuki
Yuki
Yuno
Yuno
Yuno
Yuno
Yuki
Yuki
Yuki
Yuki
Yuki
...

result:

ok 50061 lines

Test #7:

score: 10
Accepted
time: 154ms
memory: 4748kb

input:

100000 100000 1000
656 155 455 611 442 830 97 990 674 397 696 823 76 878 201 23 872 128 875 915 296 807 61 695 131 242 322 849 748 248 650 285 807 689 701 684 504 266 933 9 347 666 643 883 708 409 738 982 780 503 269 538 333 42 136 100 333 859 18 478 626 386 319 781 919 9 181 287 476 670 180 455 559...

output:

Yuki
Yuno
Yuno
Yuki
Yuki
Yuki
Yuno
Yuki
Yuki
Yuki
Yuki
Yuki
Yuki
Yuki
Yuno
Yuno
Yuno
Yuki
Yuki
Yuki
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuki
Yuki
Yuno
Yuki
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuki
Yuno
Yuki
Yuno
...

result:

ok 50143 lines

Test #8:

score: 10
Accepted
time: 149ms
memory: 4604kb

input:

100000 100000 183
41 93 102 88 179 176 87 82 55 150 125 144 158 92 10 22 62 116 83 138 111 81 163 7 30 145 117 3 113 23 40 117 0 82 31 38 42 140 44 166 113 121 147 176 181 10 53 69 180 47 120 86 171 40 27 27 109 46 155 42 119 161 64 154 5 92 0 177 101 9 130 131 60 100 152 56 15 129 67 103 82 6 143 8...

output:

Yuki
Yuki
Yuki
Yuki
Yuki
Yuno
Yuki
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuki
Yuki
Yuno
Yuno
Yuki
Yuki
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuno
Yuki
Yuki
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuki
Yuki
Yuki
Yuki
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuki
Yuno
Yuno
...

result:

ok 50149 lines

Test #9:

score: 10
Accepted
time: 146ms
memory: 4616kb

input:

100000 100000 233
6 10 176 126 110 109 129 8 196 96 225 121 185 129 29 15 45 60 13 144 181 34 177 223 120 131 113 33 151 90 6 0 27 97 136 143 59 101 120 191 6 202 47 18 109 226 213 79 117 218 150 78 196 30 187 156 169 70 229 136 17 1 207 78 144 17 5 180 37 94 175 20 17 200 202 50 48 111 193 198 81 1...

output:

Yuno
Yuki
Yuno
Yuno
Yuki
Yuki
Yuki
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuki
Yuno
Yuno
Yuno
Yuki
Yuki
Yuno
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuki
Yuki
Yuki
Yuno
Yuki
Yuki
Yuno
Yuno
Yuki
Yuno
...

result:

ok 50085 lines

Test #10:

score: 10
Accepted
time: 104ms
memory: 4548kb

input:

100000 100000 152
46 136 17 54 10 137 149 1 64 80 41 17 24 66 62 52 101 98 41 137 81 71 63 40 57 70 36 59 35 10 49 54 0 120 141 64 32 90 11 79 110 62 149 58 80 56 77 7 35 132 39 13 87 116 126 50 63 4 49 45 70 14 15 37 64 26 16 139 89 149 142 13 110 119 91 114 34 82 56 31 46 137 109 138 50 140 99 29 ...

output:

Yuno
Yuki
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuki
Yuno
Yuki
Yuki
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuki
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
Yuno
...

result:

ok 50054 lines