답안 #58851 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58851	2018-07-19T16:15:24 Z	Benq	Segments (IZhO18_segments)	C++14	55 / 100	1504 ms	41960 KB

segments

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 0;
const ll INF = 1e18;
const int MX = 200001;

int NUM = 250;
int TOT = 200000;

int n,t,ans, L[MX], R[MX];
short cbucket[MX], bucketsz[MX];
int buckety[2*MX], bucketyx[2*MX], lst[2*MX], v[MX];

bool cmp(int l, int r) {
    if (L[l] != L[r]) return L[l] < L[r];
    return l < r;
}

void rebuild() {
    int co = 0;
    F0R(i,NUM) {
        int st = 2*TOT/NUM*i;
        FOR(j,st,st+bucketsz[i]) v[co++] = lst[j];
        bucketsz[i] = 0;
    }

    F0R(i,NUM) {
        int st = 2*TOT/NUM*i;
        
        FOR(j,i*co/NUM,(i+1)*co/NUM) {
            cbucket[v[j]] = i;
            int ind = st+bucketsz[i];
            buckety[ind] = R[v[j]];
            bucketyx[ind] = R[v[j]]-L[v[j]];
            lst[ind] = v[j];
            bucketsz[i] ++;
        }

        int en = st+bucketsz[i];
        sort(buckety+st,buckety+en);
        sort(bucketyx+st,bucketyx+en);
    }
}

void ins(int* v0, int* v1, int x, int ad = 1) {
    auto it = lb(v0,v1,x);
    if (ad == 1) {
        *v1 = x; 
        rotate(it,v1,v1+1);
    } else {
        rotate(it,it+1,v1);
    }
}

void insLst(int* v0, int* v1, int x, int ad = 1) {
    auto it = lb(v0,v1,x,cmp);
    if (ad == 1) {
        *v1 = x; 
        rotate(it,v1,v1+1);
    } else {
        rotate(it,it+1,v1);
    }
}

void INS(int id, int ad = 1) {
    int b = cbucket[id];
    int st = 2*TOT/NUM*b, en = st+bucketsz[b];
    
    ins(buckety+st,buckety+en,R[id],ad);
    ins(bucketyx+st,bucketyx+en,R[id]-L[id],ad);
    insLst(lst+st,lst+en,id,ad);
    
    bucketsz[b] += ad;
}

void upd(int id, int l, int r) {
    L[id] = l, R[id] = r;
    int b = 0; 
    while (b+1 < NUM && (bucketsz[b] == 0 || cmp(lst[2*TOT/NUM*b+bucketsz[b]-1],id))) b ++;
    cbucket[id] = b;
    INS(id);
}

int hix, loy, loyx;

int manual(int x, int l) {
    int t = 0;
    FOR(i,2*TOT/NUM*x,2*TOT/NUM*x+bucketsz[x]) {
        if (L[lst[i]] > hix) continue;
        if (L[lst[i]] > l) t += (R[lst[i]]-L[lst[i]] >= loyx);
        else t += (R[lst[i]] >= loy);
    }
    return t;
}

int atLeast(int* l, int* r, int y) {
    return distance(lb(l,r,y),r);
}

int query(int l, int r, int k) {
    if (k > r-l+1) return 0;
    hix = r-k+1, loy = l+k-1, loyx = k-1;
    
    int ans = 0, clst = -MOD;
    F0R(i,NUM) if (bucketsz[i]) {
        int st = 2*TOT/NUM*i, en = st+bucketsz[i];
        int x = lst[en-1];
        
        if (L[x] > hix) {
            ans += manual(i,l);
            break;
        } else if (L[x] > l) {
            if (clst <= l) ans += manual(i,l);
            else ans += atLeast(bucketyx+st,bucketyx+en,loyx);
        } else {
            ans += atLeast(buckety+st,buckety+en,loy);
        }
        
        clst = L[x];
    }   

    return ans;
}

int getR() {
    return rand() % (1<<30);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> t;
    
    int cur = 0, nex = 1;
    F0R(i,n) {
        // int z = 2*(rand()&1)+1; 
        int z; cin >> z;
        if (z == 1) {
            // int l = getR(),r = getR(); 
            int l,r; cin >> l >> r;
            l ^= (t*ans), r ^= (t*ans);
            if (l > r) swap(l,r);
            upd(nex++,l,r);
        } else if (z == 2) {
            int id; cin >> id;
            INS(id,-1);
        } else {
            // int l = getR(),r = getR(),k = 500; 
            int l,r,k; cin >> l >> r >> k;
            l ^= (t*ans), r ^= (t*ans);
            if (l > r) swap(l,r);
            ans = query(l,r,k);
            cout << ans << "\n";
        }
        cur ++;
        if (cur % (TOT/NUM) == 0) rebuild();
    }
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	3 ms	504 KB	Output is correct
3	Correct	8 ms	1948 KB	Output is correct
4	Correct	11 ms	1948 KB	Output is correct
5	Correct	19 ms	3836 KB	Output is correct
6	Correct	20 ms	3924 KB	Output is correct
7	Correct	13 ms	3924 KB	Output is correct
8	Correct	17 ms	3940 KB	Output is correct
9	Correct	18 ms	3940 KB	Output is correct
10	Correct	15 ms	3940 KB	Output is correct
11	Correct	27 ms	3940 KB	Output is correct
12	Correct	27 ms	4000 KB	Output is correct
13	Correct	16 ms	4004 KB	Output is correct
14	Correct	18 ms	4144 KB	Output is correct
15	Correct	10 ms	4144 KB	Output is correct
16	Correct	11 ms	4144 KB	Output is correct
17	Correct	21 ms	4300 KB	Output is correct
18	Correct	13 ms	4316 KB	Output is correct
19	Correct	17 ms	4320 KB	Output is correct
20	Correct	16 ms	4320 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1358 ms	5856 KB	Output is correct
2	Correct	1287 ms	5916 KB	Output is correct
3	Correct	1457 ms	5916 KB	Output is correct
4	Correct	1504 ms	6080 KB	Output is correct
5	Correct	1089 ms	6720 KB	Output is correct
6	Correct	885 ms	6948 KB	Output is correct
7	Correct	1323 ms	6948 KB	Output is correct
8	Correct	1303 ms	6948 KB	Output is correct
9	Correct	1246 ms	6948 KB	Output is correct
10	Correct	1117 ms	6948 KB	Output is correct
11	Correct	1203 ms	6948 KB	Output is correct
12	Correct	1443 ms	6948 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	130 ms	6948 KB	Output is correct
2	Correct	95 ms	6948 KB	Output is correct
3	Correct	181 ms	6948 KB	Output is correct
4	Correct	92 ms	6948 KB	Output is correct
5	Correct	1377 ms	6948 KB	Output is correct
6	Correct	1258 ms	6948 KB	Output is correct
7	Correct	1397 ms	6948 KB	Output is correct
8	Correct	1051 ms	6948 KB	Output is correct
9	Correct	983 ms	6948 KB	Output is correct
10	Correct	996 ms	6948 KB	Output is correct
11	Correct	315 ms	6948 KB	Output is correct
12	Correct	927 ms	6948 KB	Output is correct
13	Correct	939 ms	6948 KB	Output is correct
14	Correct	709 ms	6948 KB	Output is correct
15	Correct	690 ms	6948 KB	Output is correct
16	Correct	580 ms	6948 KB	Output is correct
17	Correct	1426 ms	6948 KB	Output is correct
18	Correct	1439 ms	6948 KB	Output is correct
19	Correct	1454 ms	6948 KB	Output is correct
20	Correct	1457 ms	6948 KB	Output is correct
21	Correct	378 ms	6948 KB	Output is correct
22	Correct	814 ms	6948 KB	Output is correct
23	Correct	948 ms	6948 KB	Output is correct
24	Correct	903 ms	6948 KB	Output is correct
25	Correct	166 ms	6948 KB	Output is correct
26	Correct	115 ms	6948 KB	Output is correct
27	Correct	157 ms	6948 KB	Output is correct
28	Correct	120 ms	6948 KB	Output is correct
29	Correct	1039 ms	6948 KB	Output is correct
30	Correct	918 ms	6948 KB	Output is correct
31	Correct	1000 ms	6948 KB	Output is correct
32	Correct	1068 ms	6948 KB	Output is correct
33	Correct	1012 ms	6948 KB	Output is correct
34	Correct	722 ms	6948 KB	Output is correct
35	Correct	895 ms	6948 KB	Output is correct
36	Correct	1016 ms	6948 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	88 ms	6948 KB	Output is correct
2	Correct	93 ms	6948 KB	Output is correct
3	Correct	96 ms	6948 KB	Output is correct
4	Correct	118 ms	6948 KB	Output is correct
5	Correct	1288 ms	7056 KB	Output is correct
6	Correct	1010 ms	7056 KB	Output is correct
7	Correct	1309 ms	7128 KB	Output is correct
8	Correct	1123 ms	7128 KB	Output is correct
9	Correct	729 ms	7128 KB	Output is correct
10	Correct	980 ms	7128 KB	Output is correct
11	Correct	450 ms	7128 KB	Output is correct
12	Correct	897 ms	7408 KB	Output is correct
13	Correct	1018 ms	7408 KB	Output is correct
14	Correct	742 ms	7408 KB	Output is correct
15	Correct	930 ms	7408 KB	Output is correct
16	Correct	1002 ms	7408 KB	Output is correct
17	Correct	1345 ms	7408 KB	Output is correct
18	Correct	1345 ms	9196 KB	Output is correct
19	Correct	1412 ms	11912 KB	Output is correct
20	Correct	1432 ms	14564 KB	Output is correct

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	3 ms	504 KB	Output is correct
3	Correct	8 ms	1948 KB	Output is correct
4	Correct	11 ms	1948 KB	Output is correct
5	Correct	19 ms	3836 KB	Output is correct
6	Correct	20 ms	3924 KB	Output is correct
7	Correct	13 ms	3924 KB	Output is correct
8	Correct	17 ms	3940 KB	Output is correct
9	Correct	18 ms	3940 KB	Output is correct
10	Correct	15 ms	3940 KB	Output is correct
11	Correct	27 ms	3940 KB	Output is correct
12	Correct	27 ms	4000 KB	Output is correct
13	Correct	16 ms	4004 KB	Output is correct
14	Correct	18 ms	4144 KB	Output is correct
15	Correct	10 ms	4144 KB	Output is correct
16	Correct	11 ms	4144 KB	Output is correct
17	Correct	21 ms	4300 KB	Output is correct
18	Correct	13 ms	4316 KB	Output is correct
19	Correct	17 ms	4320 KB	Output is correct
20	Correct	16 ms	4320 KB	Output is correct
21	Correct	1358 ms	5856 KB	Output is correct
22	Correct	1287 ms	5916 KB	Output is correct
23	Correct	1457 ms	5916 KB	Output is correct
24	Correct	1504 ms	6080 KB	Output is correct
25	Correct	1089 ms	6720 KB	Output is correct
26	Correct	885 ms	6948 KB	Output is correct
27	Correct	1323 ms	6948 KB	Output is correct
28	Correct	1303 ms	6948 KB	Output is correct
29	Correct	1246 ms	6948 KB	Output is correct
30	Correct	1117 ms	6948 KB	Output is correct
31	Correct	1203 ms	6948 KB	Output is correct
32	Correct	1443 ms	6948 KB	Output is correct
33	Correct	88 ms	6948 KB	Output is correct
34	Correct	93 ms	6948 KB	Output is correct
35	Correct	96 ms	6948 KB	Output is correct
36	Correct	118 ms	6948 KB	Output is correct
37	Correct	1288 ms	7056 KB	Output is correct
38	Correct	1010 ms	7056 KB	Output is correct
39	Correct	1309 ms	7128 KB	Output is correct
40	Correct	1123 ms	7128 KB	Output is correct
41	Correct	729 ms	7128 KB	Output is correct
42	Correct	980 ms	7128 KB	Output is correct
43	Correct	450 ms	7128 KB	Output is correct
44	Correct	897 ms	7408 KB	Output is correct
45	Correct	1018 ms	7408 KB	Output is correct
46	Correct	742 ms	7408 KB	Output is correct
47	Correct	930 ms	7408 KB	Output is correct
48	Correct	1002 ms	7408 KB	Output is correct
49	Correct	1345 ms	7408 KB	Output is correct
50	Correct	1345 ms	9196 KB	Output is correct
51	Correct	1412 ms	11912 KB	Output is correct
52	Correct	1432 ms	14564 KB	Output is correct
53	Correct	137 ms	15368 KB	Output is correct
54	Correct	140 ms	17548 KB	Output is correct
55	Correct	99 ms	19700 KB	Output is correct
56	Correct	108 ms	21724 KB	Output is correct
57	Correct	1374 ms	25436 KB	Output is correct
58	Correct	931 ms	28000 KB	Output is correct
59	Correct	1342 ms	31656 KB	Output is correct
60	Correct	842 ms	33380 KB	Output is correct
61	Correct	968 ms	36700 KB	Output is correct
62	Correct	1028 ms	39524 KB	Output is correct
63	Runtime error	952 ms	41960 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
64	Halted	0 ms	0 KB	-

Subtask #6
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	3 ms	504 KB	Output is correct
3	Correct	8 ms	1948 KB	Output is correct
4	Correct	11 ms	1948 KB	Output is correct
5	Correct	19 ms	3836 KB	Output is correct
6	Correct	20 ms	3924 KB	Output is correct
7	Correct	13 ms	3924 KB	Output is correct
8	Correct	17 ms	3940 KB	Output is correct
9	Correct	18 ms	3940 KB	Output is correct
10	Correct	15 ms	3940 KB	Output is correct
11	Correct	27 ms	3940 KB	Output is correct
12	Correct	27 ms	4000 KB	Output is correct
13	Correct	16 ms	4004 KB	Output is correct
14	Correct	18 ms	4144 KB	Output is correct
15	Correct	10 ms	4144 KB	Output is correct
16	Correct	11 ms	4144 KB	Output is correct
17	Correct	21 ms	4300 KB	Output is correct
18	Correct	13 ms	4316 KB	Output is correct
19	Correct	17 ms	4320 KB	Output is correct
20	Correct	16 ms	4320 KB	Output is correct
21	Correct	1358 ms	5856 KB	Output is correct
22	Correct	1287 ms	5916 KB	Output is correct
23	Correct	1457 ms	5916 KB	Output is correct
24	Correct	1504 ms	6080 KB	Output is correct
25	Correct	1089 ms	6720 KB	Output is correct
26	Correct	885 ms	6948 KB	Output is correct
27	Correct	1323 ms	6948 KB	Output is correct
28	Correct	1303 ms	6948 KB	Output is correct
29	Correct	1246 ms	6948 KB	Output is correct
30	Correct	1117 ms	6948 KB	Output is correct
31	Correct	1203 ms	6948 KB	Output is correct
32	Correct	1443 ms	6948 KB	Output is correct
33	Correct	130 ms	6948 KB	Output is correct
34	Correct	95 ms	6948 KB	Output is correct
35	Correct	181 ms	6948 KB	Output is correct
36	Correct	92 ms	6948 KB	Output is correct
37	Correct	1377 ms	6948 KB	Output is correct
38	Correct	1258 ms	6948 KB	Output is correct
39	Correct	1397 ms	6948 KB	Output is correct
40	Correct	1051 ms	6948 KB	Output is correct
41	Correct	983 ms	6948 KB	Output is correct
42	Correct	996 ms	6948 KB	Output is correct
43	Correct	315 ms	6948 KB	Output is correct
44	Correct	927 ms	6948 KB	Output is correct
45	Correct	939 ms	6948 KB	Output is correct
46	Correct	709 ms	6948 KB	Output is correct
47	Correct	690 ms	6948 KB	Output is correct
48	Correct	580 ms	6948 KB	Output is correct
49	Correct	1426 ms	6948 KB	Output is correct
50	Correct	1439 ms	6948 KB	Output is correct
51	Correct	1454 ms	6948 KB	Output is correct
52	Correct	1457 ms	6948 KB	Output is correct
53	Correct	378 ms	6948 KB	Output is correct
54	Correct	814 ms	6948 KB	Output is correct
55	Correct	948 ms	6948 KB	Output is correct
56	Correct	903 ms	6948 KB	Output is correct
57	Correct	166 ms	6948 KB	Output is correct
58	Correct	115 ms	6948 KB	Output is correct
59	Correct	157 ms	6948 KB	Output is correct
60	Correct	120 ms	6948 KB	Output is correct
61	Correct	1039 ms	6948 KB	Output is correct
62	Correct	918 ms	6948 KB	Output is correct
63	Correct	1000 ms	6948 KB	Output is correct
64	Correct	1068 ms	6948 KB	Output is correct
65	Correct	1012 ms	6948 KB	Output is correct
66	Correct	722 ms	6948 KB	Output is correct
67	Correct	895 ms	6948 KB	Output is correct
68	Correct	1016 ms	6948 KB	Output is correct
69	Correct	88 ms	6948 KB	Output is correct
70	Correct	93 ms	6948 KB	Output is correct
71	Correct	96 ms	6948 KB	Output is correct
72	Correct	118 ms	6948 KB	Output is correct
73	Correct	1288 ms	7056 KB	Output is correct
74	Correct	1010 ms	7056 KB	Output is correct
75	Correct	1309 ms	7128 KB	Output is correct
76	Correct	1123 ms	7128 KB	Output is correct
77	Correct	729 ms	7128 KB	Output is correct
78	Correct	980 ms	7128 KB	Output is correct
79	Correct	450 ms	7128 KB	Output is correct
80	Correct	897 ms	7408 KB	Output is correct
81	Correct	1018 ms	7408 KB	Output is correct
82	Correct	742 ms	7408 KB	Output is correct
83	Correct	930 ms	7408 KB	Output is correct
84	Correct	1002 ms	7408 KB	Output is correct
85	Correct	1345 ms	7408 KB	Output is correct
86	Correct	1345 ms	9196 KB	Output is correct
87	Correct	1412 ms	11912 KB	Output is correct
88	Correct	1432 ms	14564 KB	Output is correct
89	Correct	137 ms	15368 KB	Output is correct
90	Correct	140 ms	17548 KB	Output is correct
91	Correct	99 ms	19700 KB	Output is correct
92	Correct	108 ms	21724 KB	Output is correct
93	Correct	1374 ms	25436 KB	Output is correct
94	Correct	931 ms	28000 KB	Output is correct
95	Correct	1342 ms	31656 KB	Output is correct
96	Correct	842 ms	33380 KB	Output is correct
97	Correct	968 ms	36700 KB	Output is correct
98	Correct	1028 ms	39524 KB	Output is correct
99	Runtime error	952 ms	41960 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
100	Halted	0 ms	0 KB	-

답안 #58851

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 15.0 / 15.0

Subtask #3 16.0 / 16.0

Subtask #4 17.0 / 17.0

Subtask #5 0 / 20.0

Subtask #6 0 / 25.0

Subtask #1
7.0 / 7.0

Subtask #2
15.0 / 15.0

Subtask #3
16.0 / 16.0

Subtask #4
17.0 / 17.0

Subtask #5
0 / 20.0

Subtask #6
0 / 25.0