oj.uz

Submission #52243

# Submission time Handle Problem Language Result Execution time Memory
52243 2018-06-25T05:53:23 Z gs14004 Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 3000 ms 112868 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 202020;
 
namespace wavelet
{
vector<int> wavelet[2*MAXN];
vector<int> leftind[2*MAXN];
vector<int> orig[2*MAXN];
int minv[2*MAXN];
int maxv[2*MAXN];
int lchild[2*MAXN];
int rchild[2*MAXN];
int gind = 0;
 
inline int lchildind(int ind, int x)
{
    return leftind[ind][x]-1;
}
inline int rchildind(int ind, int x)
{
    return x-leftind[ind][x];
}
 
int count_ge(int from, int to, int K, int ind)
{
    //printf("=%d %d %d %d\n", from, to, K, ind);
    if(from > to) return 0;
    if(maxv[ind] < K) return 0;
    if(minv[ind] >= K) return to-from+1;
    
    int ls, rs, le, re;
    if(wavelet[ind][from] <= (maxv[ind]+minv[ind])/2)
    {
        ls = leftind[ind][from]-1;
        rs = from-ls;
    }
    else
    {
        ls = leftind[ind][from];
        rs = from-ls;
    }
    
    if(wavelet[ind][to] <= (maxv[ind]+minv[ind])/2)
    {
        le = leftind[ind][to]-1;
        re = to-1-le;
    }
    else
    {
        le = leftind[ind][to]-1;
        re = to-1-le;
    }
    
    return count_ge(ls, le, K, lchild[ind])
         + count_ge(rs, re, K, rchild[ind]);
}
 
int find_inside(int from, int to, int ind)
{
    if(from > to) return -1;
    if(to < minv[ind]) return -1;
    if(maxv[ind] < from) return -1;
    
    if(from <= minv[ind] && maxv[ind] <= to)
        return orig[ind].back();
 
    return max(find_inside(from, to, lchild[ind]), find_inside(from, to, rchild[ind]));
}
 
int find_inside(int from, int to)
{
    int N = wavelet[0].size();
    int lo = -1; //here must be answer
    int hi = N; //here mustn't be answer;
    while(lo+1!=hi)
    {
        int mi = (lo+hi)/2;
        int cntl = count_ge(mi, N-1, to+1, 0);
        int cntr = count_ge(mi, N-1, from, 0);
        //printf("%d %d %d [%d, %d]\n", mi, cntl, cntr, from, to);
        if(cntl != cntr) lo = mi;
        else hi = mi;
    }
    return lo;
}
 
void build_wavelet(int ind)
{
    int N = wavelet[ind].size();
    minv[ind] = *min_element(wavelet[ind].begin(), wavelet[ind].end());
    maxv[ind] = *max_element(wavelet[ind].begin(), wavelet[ind].end());
    if(minv[ind] == maxv[ind]) return;
    lchild[ind] = gind++;
    rchild[ind] = gind++;
    int midv = (minv[ind]+maxv[ind])/2;
    //minv[ind] ~ midv, midv+1, maxv[ind]
    int p = 0;
    for(int i=0; i<N; ++i)
    {
        if(wavelet[ind][i] <= midv)
        {
            ++p;
            wavelet[lchild[ind]].push_back(wavelet[ind][i]);
            orig[lchild[ind]].push_back(orig[ind][i]);
        }
        else
        {
            wavelet[rchild[ind]].push_back(wavelet[ind][i]);
            orig[rchild[ind]].push_back(orig[ind][i]);
        }
        leftind[ind].push_back(p);
    }
    build_wavelet(lchild[ind]);
    build_wavelet(rchild[ind]);
}
 
 
};
 
int N, K;
int A[MAXN];
int B[MAXN];
int T[MAXN];
int main()
{
    scanf("%d%d", &N, &K);
    for(int i=0; i<N; ++i)
        scanf("%d%d", A+i, B+i);
    
    for(int i=0; i<K; ++i)
    {
        int t; scanf("%d", &t);
        wavelet::wavelet[wavelet::gind].push_back(t);
        wavelet::orig[wavelet::gind].push_back(i);
    }
    wavelet::build_wavelet(wavelet::gind++);
 
  
    long long ans = 0;
    for(int i=0; i<N; ++i)
    {
        int small = min(A[i], B[i]);
        int large = max(A[i], B[i]);
        int ind = wavelet::find_inside(small, large-1);
        int now = A[i];
        if(ind != -1) now = large;
        int cnt = wavelet::count_ge(ind+1, K-1, large, 0);
        if(cnt&1) now = small+large-now;
        ans += now;
        //printf("%d %d %d\n", ind, cnt, now);
    }
    printf("%lld\n", ans);
    
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:127:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &K);
     ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:129:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", A+i, B+i);
         ~~~~~^~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:133:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int t; scanf("%d", &t);
                ~~~~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 29176 KB Output is correct
2 Correct 29 ms 29260 KB Output is correct
3 Correct 30 ms 29260 KB Output is correct
4 Correct 29 ms 29260 KB Output is correct
5 Correct 29 ms 29260 KB Output is correct
6 Correct 30 ms 29260 KB Output is correct
7 Correct 30 ms 29260 KB Output is correct
8 Correct 30 ms 29288 KB Output is correct
9 Correct 27 ms 29320 KB Output is correct
10 Correct 27 ms 29320 KB Output is correct
11 Correct 29 ms 29320 KB Output is correct
12 Correct 29 ms 29392 KB Output is correct
13 Correct 30 ms 29400 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 29176 KB Output is correct
2 Correct 29 ms 29260 KB Output is correct
3 Correct 30 ms 29260 KB Output is correct
4 Correct 29 ms 29260 KB Output is correct
5 Correct 29 ms 29260 KB Output is correct
6 Correct 30 ms 29260 KB Output is correct
7 Correct 30 ms 29260 KB Output is correct
8 Correct 30 ms 29288 KB Output is correct
9 Correct 27 ms 29320 KB Output is correct
10 Correct 27 ms 29320 KB Output is correct
11 Correct 29 ms 29320 KB Output is correct
12 Correct 29 ms 29392 KB Output is correct
13 Correct 30 ms 29400 KB Output is correct
14 Correct 92 ms 32984 KB Output is correct
15 Correct 185 ms 37160 KB Output is correct
16 Correct 280 ms 40276 KB Output is correct
17 Correct 405 ms 45672 KB Output is correct
18 Correct 414 ms 45800 KB Output is correct
19 Correct 387 ms 45800 KB Output is correct
20 Correct 420 ms 45800 KB Output is correct
21 Correct 324 ms 45844 KB Output is correct
22 Correct 202 ms 45844 KB Output is correct
23 Correct 204 ms 45844 KB Output is correct
24 Correct 205 ms 45844 KB Output is correct
25 Correct 202 ms 45844 KB Output is correct
26 Correct 330 ms 45844 KB Output is correct
27 Correct 442 ms 45844 KB Output is correct
28 Correct 226 ms 45844 KB Output is correct
29 Correct 526 ms 45844 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 29176 KB Output is correct
2 Correct 29 ms 29260 KB Output is correct
3 Correct 30 ms 29260 KB Output is correct
4 Correct 29 ms 29260 KB Output is correct
5 Correct 29 ms 29260 KB Output is correct
6 Correct 30 ms 29260 KB Output is correct
7 Correct 30 ms 29260 KB Output is correct
8 Correct 30 ms 29288 KB Output is correct
9 Correct 27 ms 29320 KB Output is correct
10 Correct 27 ms 29320 KB Output is correct
11 Correct 29 ms 29320 KB Output is correct
12 Correct 29 ms 29392 KB Output is correct
13 Correct 30 ms 29400 KB Output is correct
14 Correct 92 ms 32984 KB Output is correct
15 Correct 185 ms 37160 KB Output is correct
16 Correct 280 ms 40276 KB Output is correct
17 Correct 405 ms 45672 KB Output is correct
18 Correct 414 ms 45800 KB Output is correct
19 Correct 387 ms 45800 KB Output is correct
20 Correct 420 ms 45800 KB Output is correct
21 Correct 324 ms 45844 KB Output is correct
22 Correct 202 ms 45844 KB Output is correct
23 Correct 204 ms 45844 KB Output is correct
24 Correct 205 ms 45844 KB Output is correct
25 Correct 202 ms 45844 KB Output is correct
26 Correct 330 ms 45844 KB Output is correct
27 Correct 442 ms 45844 KB Output is correct
28 Correct 226 ms 45844 KB Output is correct
29 Correct 526 ms 45844 KB Output is correct
30 Correct 557 ms 111308 KB Output is correct
31 Correct 1087 ms 111660 KB Output is correct
32 Correct 1716 ms 112232 KB Output is correct
33 Execution timed out 3058 ms 112868 KB Time limit exceeded
34 Halted 0 ms 0 KB -