Submission #433287

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
433287	2021-06-19T12:50:28 Z	mat_v	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	4 ms	5068 KB

fortune_telling2

#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,n);

    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;
        }

        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);
    }
    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:130:5: note: in expansion of macro 'ff'
  130 |     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:134:5: note: in expansion of macro 'ff'
  134 |     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:135:5: note: in expansion of macro 'fb'
  135 |     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:144:5: note: in expansion of macro 'ff'
  144 |     ff(i,1,n)sum += orig[i].xx;
      |     ^~

Subtask #1

0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	5068 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	5068 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	5068 KB	Output isn't correct
2	Halted	0 ms	0 KB	-