oj.uz

Submission #434245

# Submission time Handle Problem Language Result Execution time Memory
434245 2021-06-20T19:12:29 Z mat_v Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 1135 ms 96456 KB 
#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define pii pair<int,int>
#define xx first
#define yy second
#define pb push_back

using namespace std;
typedef long long ll;

int n,k;
pii niz[200005];
pii val[200005];
int seg[4 * 200005];
void init(int node, int l, int r){
    if(l == r){
        seg[node] = val[l].yy;
        return;
    }
    int mid = (l + r) / 2;
    init(node * 2, l, mid);
    init(node * 2 + 1, mid + 1, r);
    seg[node] = max(seg[node * 2], seg[node * 2 + 1]);
}
int kveri(int node, int l, int r, int levo, int desno){
    if(l > r || levo > desno || l > desno || levo > r)return 0;
    if(l >= levo && r <= desno)return seg[node];
    int mid = (l + r) / 2;
    return max(kveri(node * 2, l, mid, levo, desno), kveri(node * 2 + 1, mid + 1, r, levo, desno));
}

vector<int> kv[200005];
bool cmp2(pii a, pii b){
    return a.yy < b.yy;
}

map<int,int>poj;
int bit[400005];
pii orig[400005];
void update(int x){
    while(x>0){
        bit[x]++;
        x -= (x&-x);
    }
}
int query(int x){
    int ans = 0;
    while(x<=400000){
        ans += bit[x];
        x += (x&-x);
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> k;
    ff(i,1,n){
        cin >> niz[i].xx;
        cin >> niz[i].yy;
        //orig[i] = niz[i];
    }
    ff(i,1,k){
        cin >> val[i].xx;
        val[i].yy = i;
    }
    sort(val + 1, val + k + 1);
    init(1,1,k);

    ff(i,1,n){
        int mn = min(niz[i].xx,niz[i].yy);
        int mx = max(niz[i].xx,niz[i].yy);
        mx--;
        int l = 1;
        int r = k;
        int levo = -1;
        if(val[k].xx >= mn){
            while(l < r){
                int mid = (l + r) / 2;
                if(val[mid].xx >= mn)r = mid;
                else l = mid + 1;
            }
            levo = l;
        }

        int desno = -1;
        l = 1;
        r = k;
        if(val[1].xx <= mx){
            while(l < r){
                int mid = (l + r + 1) / 2;
                if(val[mid].xx <= mx)l = mid;

                else r = mid - 1;
            }
            desno = l;
        }
        //cout << levo << " " << desno << "\n";
        if(desno == -1 || levo == -1 || levo > desno){
            //cout << i << "\n";
            kv[1].pb(i);
            continue;
        }
        if(levo <= desno){
            kv[kveri(1,1,k,levo,desno)].pb(i);
            if(niz[i].xx <= niz[i].yy)swap(niz[i].xx, niz[i].yy);
            continue;
        }
    }

    sort(val + 1, val + k + 1, cmp2);

    vector<int> svi;
    ff(i,1,k)svi.pb(val[i].xx);
    ff(i,1,n){
        svi.pb(niz[i].xx);
        svi.pb(niz[i].yy);
    }
    ff(i,1,n)orig[i] = niz[i];
    sort(svi.begin(), svi.end());
    int last = -1;
    int br=1;
    for(auto c:svi){
        if(c == last)continue;
        poj[c] = br;
        br++;
        last = c;
    }
    ff(i,1,n){
        niz[i].xx = poj[niz[i].xx];
        niz[i].yy = poj[niz[i].yy];
    }
    ff(i,1,k)val[i].xx = poj[val[i].xx];
    fb(i,k,1){
        update(val[i].xx);
        for(auto c:kv[i]){
            int sta = query(max(niz[c].xx, niz[c].yy));
            if(sta%2 == 1)swap(orig[c].xx,orig[c].yy);
        }

    }
    ll sum = 0;
    ff(i,1,n)sum += orig[i].xx;

    cout << sum << "\n";
    return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
fortune_telling2.cpp:60:5: note: in expansion of macro 'ff'
   60 |     ff(i,1,n){
      |     ^~
fortune_telling2.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
fortune_telling2.cpp:65:5: note: in expansion of macro 'ff'
   65 |     ff(i,1,k){
      |     ^~
fortune_telling2.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
fortune_telling2.cpp:72:5: note: in expansion of macro 'ff'
   72 |     ff(i,1,n){
      |     ^~
fortune_telling2.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
fortune_telling2.cpp:116:5: note: in expansion of macro 'ff'
  116 |     ff(i,1,k)svi.pb(val[i].xx);
      |     ^~
fortune_telling2.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
fortune_telling2.cpp:117:5: note: in expansion of macro 'ff'
  117 |     ff(i,1,n){
      |     ^~
fortune_telling2.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
fortune_telling2.cpp:121:5: note: in expansion of macro 'ff'
  121 |     ff(i,1,n)orig[i] = niz[i];
      |     ^~
fortune_telling2.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
fortune_telling2.cpp:131:5: note: in expansion of macro 'ff'
  131 |     ff(i,1,n){
      |     ^~
fortune_telling2.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
fortune_telling2.cpp:135:5: note: in expansion of macro 'ff'
  135 |     ff(i,1,k)val[i].xx = poj[val[i].xx];
      |     ^~
fortune_telling2.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
fortune_telling2.cpp:136:5: note: in expansion of macro 'fb'
  136 |     fb(i,k,1){
      |     ^~
fortune_telling2.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
fortune_telling2.cpp:145:5: note: in expansion of macro 'ff'
  145 |     ff(i,1,n)sum += orig[i].xx;
      |     ^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 5 ms 5196 KB Output is correct
3 Correct 6 ms 5196 KB Output is correct
4 Correct 5 ms 5196 KB Output is correct
5 Correct 5 ms 5196 KB Output is correct
6 Correct 6 ms 5196 KB Output is correct
7 Correct 5 ms 5196 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct
9 Correct 5 ms 5196 KB Output is correct
10 Correct 5 ms 5196 KB Output is correct
11 Correct 5 ms 5196 KB Output is correct
12 Correct 5 ms 5168 KB Output is correct
13 Correct 5 ms 5196 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 5 ms 5196 KB Output is correct
3 Correct 6 ms 5196 KB Output is correct
4 Correct 5 ms 5196 KB Output is correct
5 Correct 5 ms 5196 KB Output is correct
6 Correct 6 ms 5196 KB Output is correct
7 Correct 5 ms 5196 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct
9 Correct 5 ms 5196 KB Output is correct
10 Correct 5 ms 5196 KB Output is correct
11 Correct 5 ms 5196 KB Output is correct
12 Correct 5 ms 5168 KB Output is correct
13 Correct 5 ms 5196 KB Output is correct
14 Correct 29 ms 7372 KB Output is correct
15 Correct 60 ms 9644 KB Output is correct
16 Correct 98 ms 11852 KB Output is correct
17 Correct 128 ms 14344 KB Output is correct
18 Correct 129 ms 14356 KB Output is correct
19 Correct 136 ms 14400 KB Output is correct
20 Correct 140 ms 14416 KB Output is correct
21 Correct 123 ms 14316 KB Output is correct
22 Correct 87 ms 11840 KB Output is correct
23 Correct 87 ms 10768 KB Output is correct
24 Correct 77 ms 10024 KB Output is correct
25 Correct 90 ms 12388 KB Output is correct
26 Correct 87 ms 11664 KB Output is correct
27 Correct 107 ms 12412 KB Output is correct
28 Correct 96 ms 12344 KB Output is correct
29 Correct 115 ms 13504 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 5 ms 5196 KB Output is correct
3 Correct 6 ms 5196 KB Output is correct
4 Correct 5 ms 5196 KB Output is correct
5 Correct 5 ms 5196 KB Output is correct
6 Correct 6 ms 5196 KB Output is correct
7 Correct 5 ms 5196 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct
9 Correct 5 ms 5196 KB Output is correct
10 Correct 5 ms 5196 KB Output is correct
11 Correct 5 ms 5196 KB Output is correct
12 Correct 5 ms 5168 KB Output is correct
13 Correct 5 ms 5196 KB Output is correct
14 Correct 29 ms 7372 KB Output is correct
15 Correct 60 ms 9644 KB Output is correct
16 Correct 98 ms 11852 KB Output is correct
17 Correct 128 ms 14344 KB Output is correct
18 Correct 129 ms 14356 KB Output is correct
19 Correct 136 ms 14400 KB Output is correct
20 Correct 140 ms 14416 KB Output is correct
21 Correct 123 ms 14316 KB Output is correct
22 Correct 87 ms 11840 KB Output is correct
23 Correct 87 ms 10768 KB Output is correct
24 Correct 77 ms 10024 KB Output is correct
25 Correct 90 ms 12388 KB Output is correct
26 Correct 87 ms 11664 KB Output is correct
27 Correct 107 ms 12412 KB Output is correct
28 Correct 96 ms 12344 KB Output is correct
29 Correct 115 ms 13504 KB Output is correct
30 Correct 274 ms 23048 KB Output is correct
31 Correct 441 ms 29004 KB Output is correct
32 Correct 609 ms 36352 KB Output is correct
33 Runtime error 1135 ms 96456 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -