oj.uz

Submission #535452

# Submission time Handle Problem Language Result Execution time Memory
535452 2022-03-10T09:44:22 Z fadi57 Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 137 ms 29132 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
const int mx= 700 * 1000 + 3;
const int mx2=1e6+9;
typedef long long ll;
const int mod=998244353 ;
const int SQ=400;
const ll inf=1e9+10;
vector<int>cord,q[mx];
int seg[mx<<2],a[mx],b[mx],T[mx],aa[mx], bb[mx];
tree<int,null_type,greater_equal<int>,rb_tree_tag,tree_order_statistics_node_update> s;
int sz;int t;int n,k;
struct fenwick{
    int n, fen[600005];
    void resize(int _n){
        n = _n + 1;
        memset(fen, 0, sizeof fen);
    }
    int query(int ind){
        int ans = 0;
        while(ind >= 1){
            ans += fen[ind];
            ind -= ind & -ind;
        }
        return ans;
    }
    void update(int ind, ll val){
        while(ind <= n){
            fen[ind] += val;
            ind += ind & -ind;
        }
    }
    int query(int l, int r){
        return query(r) - query(l - 1);
    }
};
fenwick fen;
int combin(int x,int y){
  if(t==0){
    return (max(x,y));
  }else{
    return x+y;
  }

}
void update(int node,int l,int r,int idx,int val){
   if(l==r){
    seg[node]=val;
    return;
   }
    int mid=(l+r)/2;
    if(idx<=mid){
    update(node*2,l,mid,idx,val);
   }else{
    update(node*2+1,mid+1,r,idx,val);
   }
   seg[node]=combin(seg[node*2],seg[node*2+1]);
    return;
  }
  int query(int node,int l,int r,int left,int right){
         if(r<left||l>right){
            if(t){return 0;}
            return -1;
      }
  if(l>=left&&r<=right){
        return seg[node];
     }
     int mid=(l+r)/2;
     return combin(query(node*2,l,mid,left,right), query(node*2+1,mid+1,r,left,right));
     }


int fin(int x){
  return upper_bound(cord.begin(),cord.end(),x)-cord.begin();
  }

 int main(){
  cin>>n>>k;
  for(int i=0;i<n;i++){
    cin>>a[i]>>b[i];
    aa[i]=a[i];
    bb[i]=b[i];
    cord.push_back(a[i]);
    cord.push_back(b[i]);
  }
for(int i=0;i<k;i++){
     cin>>T[i];
     cord.push_back(T[i]);
  }
cord.erase(unique(cord.begin() , cord.end()) , cord.end()) ;sort(cord.begin(),cord.end());
sz=2*n+k;

for(int i=0;i<n;i++){
    a[i]=fin(a[i]);
    b[i]=fin(b[i]);
  }
   memset(seg,-1,sizeof(seg));
   for(int i=0;i<k;i++){
    T[i]=fin(T[i]);
    update(1,0,sz,T[i],i);
    }
  for(int i=0;i<n;i++){
    int idx=query(1,0,sz,min(a[i],b[i]),max(a[i],b[i])-1);
     q[idx+1].push_back(i);
    }
  t=1;
   ll ans=0;  memset(seg,0,sizeof(seg));
   for (int i=k;i>=0;i--)
	{
	    if(i!=k){ update(1,0,sz,T[i],1);}
        for (int j:q[i])
		{   int parity;
			parity=query(1,0,sz,max(a[j],b[j]),sz)%2;
		if(i==0)
    		parity ^= a[j] < b[j];
         if(parity){
            ans+=min(bb[j],aa[j]);

         }else{
          ans+=max(bb[j],aa[j]);

          }
    	//cout<<i<<" "<<j<<" "<<parity<<"\n";
    	}
    	}
    	cout<<ans;
    	}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 27732 KB Output is correct
2 Correct 20 ms 27780 KB Output is correct
3 Correct 20 ms 27712 KB Output is correct
4 Correct 19 ms 27740 KB Output is correct
5 Correct 26 ms 27828 KB Output is correct
6 Correct 17 ms 27776 KB Output is correct
7 Correct 21 ms 27732 KB Output is correct
8 Correct 18 ms 27820 KB Output is correct
9 Correct 23 ms 27820 KB Output is correct
10 Correct 18 ms 27768 KB Output is correct
11 Correct 19 ms 27732 KB Output is correct
12 Correct 20 ms 27768 KB Output is correct
13 Correct 18 ms 27712 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 27732 KB Output is correct
2 Correct 20 ms 27780 KB Output is correct
3 Correct 20 ms 27712 KB Output is correct
4 Correct 19 ms 27740 KB Output is correct
5 Correct 26 ms 27828 KB Output is correct
6 Correct 17 ms 27776 KB Output is correct
7 Correct 21 ms 27732 KB Output is correct
8 Correct 18 ms 27820 KB Output is correct
9 Correct 23 ms 27820 KB Output is correct
10 Correct 18 ms 27768 KB Output is correct
11 Correct 19 ms 27732 KB Output is correct
12 Correct 20 ms 27768 KB Output is correct
13 Correct 18 ms 27712 KB Output is correct
14 Correct 46 ms 28424 KB Output is correct
15 Correct 73 ms 28804 KB Output is correct
16 Incorrect 137 ms 29132 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 27732 KB Output is correct
2 Correct 20 ms 27780 KB Output is correct
3 Correct 20 ms 27712 KB Output is correct
4 Correct 19 ms 27740 KB Output is correct
5 Correct 26 ms 27828 KB Output is correct
6 Correct 17 ms 27776 KB Output is correct
7 Correct 21 ms 27732 KB Output is correct
8 Correct 18 ms 27820 KB Output is correct
9 Correct 23 ms 27820 KB Output is correct
10 Correct 18 ms 27768 KB Output is correct
11 Correct 19 ms 27732 KB Output is correct
12 Correct 20 ms 27768 KB Output is correct
13 Correct 18 ms 27712 KB Output is correct
14 Correct 46 ms 28424 KB Output is correct
15 Correct 73 ms 28804 KB Output is correct
16 Incorrect 137 ms 29132 KB Output isn't correct
17 Halted 0 ms 0 KB -