oj.uz

Submission #535266

# Submission time Handle Problem Language Result Execution time Memory
535266 2022-03-09T20:51:54 Z fadi57 Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 1522 ms 9248 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=2e5+900;
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[4*mx],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;
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){

    seg[idx]=val;
    return;
   if(l==idx){
    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){
       int z=-1;
      if(t==0){

        for(int i=left;i<=right;i++){
            z=max(z,seg[i]);

        }
      }else{
         z=0;
         for(int i=left;i<=right;i++){
            z+=seg[i];

        }
      }
      return z;
      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));
     }

    void upd(int pos,int val){
       update(1,0,sz,pos,val);

    }
    int quer(int x,int y){
       return query(1,0,sz,x,y);

     }

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

  sort(cord.begin(),cord.end());
  cord.erase(unique(cord.begin() , cord.end()) , cord.end()) ;


 sz=cord.size();
    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]);
    upd(T[i],i);
  //  cout<<T[i];
    }

   for(int i=0;i<n;i++){

     int idx=quer(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){ upd(T[i],1);}
		for (int j:q[i])
		{
			int parity;
			parity=quer(max(a[j],b[j]),sz)&1;
			if(i==0)
    			parity ^= a[j] < b[j];
         if(parity){
            ans+=min(bb[j],aa[j]);
         }else{
          ans+=max(bb[j],aa[j]);
          }
    		//ans += parity ? max(bb[i],aa[i]):min(bb[i],aa[i]);
    	//	cout<<i<<" "<<j<<" "<<parity<<"\n";

		}

		//cout<<seg[3]<<endl;

	}

   cout<<ans;

  }

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 6 ms 8148 KB Output is correct
3 Correct 8 ms 8276 KB Output is correct
4 Correct 8 ms 8148 KB Output is correct
5 Correct 9 ms 8224 KB Output is correct
6 Correct 8 ms 8148 KB Output is correct
7 Correct 7 ms 8128 KB Output is correct
8 Correct 8 ms 8232 KB Output is correct
9 Correct 8 ms 8148 KB Output is correct
10 Correct 5 ms 8148 KB Output is correct
11 Correct 6 ms 8148 KB Output is correct
12 Correct 6 ms 8148 KB Output is correct
13 Correct 6 ms 8148 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 6 ms 8148 KB Output is correct
3 Correct 8 ms 8276 KB Output is correct
4 Correct 8 ms 8148 KB Output is correct
5 Correct 9 ms 8224 KB Output is correct
6 Correct 8 ms 8148 KB Output is correct
7 Correct 7 ms 8128 KB Output is correct
8 Correct 8 ms 8232 KB Output is correct
9 Correct 8 ms 8148 KB Output is correct
10 Correct 5 ms 8148 KB Output is correct
11 Correct 6 ms 8148 KB Output is correct
12 Correct 6 ms 8148 KB Output is correct
13 Correct 6 ms 8148 KB Output is correct
14 Correct 168 ms 8564 KB Output is correct
15 Correct 688 ms 8932 KB Output is correct
16 Incorrect 1522 ms 9248 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 6 ms 8148 KB Output is correct
3 Correct 8 ms 8276 KB Output is correct
4 Correct 8 ms 8148 KB Output is correct
5 Correct 9 ms 8224 KB Output is correct
6 Correct 8 ms 8148 KB Output is correct
7 Correct 7 ms 8128 KB Output is correct
8 Correct 8 ms 8232 KB Output is correct
9 Correct 8 ms 8148 KB Output is correct
10 Correct 5 ms 8148 KB Output is correct
11 Correct 6 ms 8148 KB Output is correct
12 Correct 6 ms 8148 KB Output is correct
13 Correct 6 ms 8148 KB Output is correct
14 Correct 168 ms 8564 KB Output is correct
15 Correct 688 ms 8932 KB Output is correct
16 Incorrect 1522 ms 9248 KB Output isn't correct
17 Halted 0 ms 0 KB -