Submission #1100771

#TimeUsernameProblemLanguageResultExecution timeMemory
1100771lampoopppFortune Telling 2 (JOI14_fortune_telling2)C++17
4 / 100
3072 ms16720 KiB
#include <bits/stdc++.h>
using namespace std;

const int N=2e5;
const int inf = 1e9+7;

struct segtree
{
    int val=0;
    int lazy=0;
    int mx,mn;
}st[4*N+1];

struct card
{
    int l, r;
    int s=0;
    bool operator < (const card & o) const
    {
        if(r==o.r) return l < o.l;
        return r < o.r;
    }
}a[N+1],tmp;
int s[N+1], id[N+1];

void Set(int x, int low, int hi, int i, int s, int k)
{
    if(low==hi)
    {
        st[x].mn=k;
        st[x].mx=k;
        st[x].val=s;
        return;
    }
    int mid = low+hi>>1;
    if(i<=mid) Set(x*2,low,mid,i,s,k);
    else Set(x*2+1,mid+1,hi,i,s,k);
    st[x].mx = max(st[x*2].mx, st[x*2+1].mx);
    st[x].mn = min(st[x*2].mn, st[x*2+1].mn);
}

//lazy=0 -> 0
//lazy=1 -> ^1
//lazy=2 ->|1
//lazy=3 -> &1

void operate(int& a, int b)
{
    if(b==1) {a^=1; return;}
    if(b==2) {a=1; return;}
    if(b==3) {a=0; return;}
}

void change(int& a, int b)
{
    if(a==0) {a=b; return;}
    if(b==2 || b==3) {a=b; return;}
    if(a==1 && b==1) {a=0; return;}
    if(a==2 && b==1) {a=3; return;}
    if(a==3 && b==1) {a=2; return;}
}


void push(int x)
{
    if(st[x].lazy==0) return;
    operate(st[x*2].val,st[x].lazy);
    operate(st[x*2+1].val,st[x].lazy);
    change(st[x*2].lazy,st[x].lazy);
    change(st[x*2+1].lazy,st[x].lazy);
    st[x].lazy=0;
}

void updateXOR(int x, int low, int hi, int i , int j)
{
    if(low > hi || low > j || hi<i) return;
    if(low>=i && hi<=j)
    {
        st[x].val^=1;
        if(st[x].lazy==0) {st[x].lazy=1; return;}
        if(st[x].lazy==1) {st[x].lazy=0; return;}
        if(st[x].lazy==2) {st[x].lazy=3; return;}
        if(st[x].lazy==3) {st[x].lazy=2; return;}
    }
    int mid = low+hi>>1;
    push(x);
    updateXOR(x*2,low,mid,i,j);
    updateXOR(x*2+1,mid+1,hi,i,j);
}

void updateOR(int x, int low, int hi, int i, int j, int k)
{
    if(low > hi || low > j || hi<i || st[x].mn>k) return;
    if(low>=i && hi<=j)
    {
        if(st[x].mx<=k)
        {
            st[x].val=1;
            st[x].lazy=2;
            return;
        }
    }
    int mid =low+hi>>1;
    push(x);
    updateOR(x*2,low,mid,i,j,k);
    updateOR(x*2+1,mid+1,hi,i,j,k);
}

int get(int x, int low, int hi, int i)
{
    if(low==hi) return st[x].val;
    int mid = low+hi>>1;
    push(x);
    if(i<=mid) return get(x*2,low,mid,i);
    return get(x*2+1,mid+1,hi,i);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin >> n >> k;
    for(int i=1;i<=n;++i)
    {
        cin >> a[i].l >> a[i].r;
        if(a[i].l > a[i].r)
        {
            swap(a[i].l,a[i].r);
            a[i].s=1;
        }
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i)
    {
        Set(1,1,n,i,a[i].s,a[i].l);
    }
    while(k--)
    {
        int x;
        cin >> x;
        tmp.l=inf;
        tmp.r=x;
        int p = upper_bound(a+1,a+n+1,tmp)-a-1;
        updateXOR(1,1,n,1,p);
        updateOR(1,1,n,p+1,n,x);
        //cout << p << " " << get(1,1,n,2) << '\n';
    }
    long long ans=0;
    for(int i=1;i<=n;++i)
    {
        int x = get(1,1,n,i);
        //cout << a[i].l << " " << a[i].r << " ";
        //cout << x << "\n";
        if(x==1) ans+=(long long)a[i].r;
        else ans+=(long long)a[i].l;
    }
    //cout << '\n';
    cout << ans;

}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void Set(int, int, int, int, int, int)':
fortune_telling2.cpp:35:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int mid = low+hi>>1;
      |               ~~~^~~
fortune_telling2.cpp: In function 'void updateXOR(int, int, int, int, int)':
fortune_telling2.cpp:85:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |     int mid = low+hi>>1;
      |               ~~~^~~
fortune_telling2.cpp: In function 'void updateOR(int, int, int, int, int, int)':
fortune_telling2.cpp:103:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |     int mid =low+hi>>1;
      |              ~~~^~~
fortune_telling2.cpp: In function 'int get(int, int, int, int)':
fortune_telling2.cpp:112:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |     int mid = low+hi>>1;
      |               ~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...