Submission #775598

#	Time	Username	Problem	Language	Result	Execution time	Memory
775598		Essa2006	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	4 / 100	3055 ms	10276 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
int n, k;
vector<int>A, B, T;
map<int, int>mp, inv;

void pre(){
    A.clear(), B.clear(), T.clear(), mp.clear(), inv.clear();
    A.resize(n), B.resize(n), T.resize(k);
}



void comp(){
    vector<int>S=T;
    for(int i=0;i<n;i++){
        S.push_back(A[i]);
        S.push_back(B[i]);
    }
    sort(all(S));
    int cnt=1;
    for(int i=0;i<S.size();i++){
        if(!i || S[i]!=S[i-1]){
            mp[S[i]]=cnt, inv[cnt]=S[i], cnt++;
        }
    }
    for(int i=0;i<n;i++){
        A[i]=mp[A[i]], B[i]=mp[B[i]];
    }
    for(int j=0;j<k;j++){
        T[j]=mp[T[j]];
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    pre();
    for(int i=0;i<n;i++){
        cin>>A[i]>>B[i];
    }
    for(int j=0;j<k;j++){
        cin>>T[j];
    }
    comp();
    for(int i=0;i<n;i++){
        vector<int>T2;
        int cnt=0;
        int mn=min(A[i], B[i]), mx=max(A[i], B[i]);
        for(int j=0;j<k;j++){
            if(T[j]>=mx)
                cnt++;
            else if(T[j]>=mn)
                T2.push_back(1);
            if(j==k-1 || (T[j+1]>=mn  && T[j+1]<mx)){
                if(cnt&1)
                    T2.push_back(2);
                cnt=0;
            }
                
        }
        for(int j=0;j<T2.size();j++){
            if(A[i]==mn)
                swap(A[i], B[i]);
            else if(T2[j]==2)
                swap(A[i], B[i]);
        }
    }
    ll ans=0;
    for(int i=0;i<n;i++){
        ans+=inv[A[i]];
    }
    cout<<ans;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void comp()':
fortune_telling2.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<S.size();i++){
      |                 ~^~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int j=0;j<T2.size();j++){
      |                     ~^~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65