QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#184583#5669. Traveling in Jade CityAnwar#WA 267ms20616kbC++232.9kb2023-09-20 21:34:312023-09-20 21:34:31

Judging History

你现在查看的是最新测评结果

  • [2023-09-20 21:34:31]
  • 评测
  • 测评结果:WA
  • 用时:267ms
  • 内存:20616kb
  • [2023-09-20 21:34:31]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 2e6 + 5 , MOD = 1e9 + 7 ;

vector<int> BIT[2] ;

void add(vector<int> & BIT , int i , int val)
{
    i++;
    while(i <= (int)BIT.size() )
    {
        BIT[i-1] += val;
        i += i & -i ;
    }
}

int get(vector<int> & BIT , int i)
{
    i++;
    int ans= 0;
    while(i > 0)
    {
        ans += BIT[i-1];
        i -= i & - i ;
    }
    return ans ;
}

int n ,  k ,m , q ;

ll sum[2] ;

void pri(ll x){
    if(x >= 1e9) cout << "impossible\n" ;
    else cout << x << "\n" ;
}

ll getCir(int u , int v)
{
    if(u > v)swap(u , v);

    ll dis = get(BIT[0] , v-1) - get(BIT[0] , u-1)  ;

    return min(  dis , sum[0] - dis ) ;
}


ll getLin(int u , int v)
{
    if(u > v) swap(u , v ) ;

    ll dis = get(BIT[1] , v-1) - get(BIT[1] , u-1)  ;

    return min(  dis , sum[1] - dis + getCir(1 , k) ) ;
}

bool val[N];

int main()
{
    cin.tie(0);cin.sync_with_stdio(0);
    cout.tie(0);cout.sync_with_stdio(0);


    cin >> n >> k >> m >> q;

    BIT[0].resize(n+5) ;

    int a[n+1] , b[m+2] ;

    for(int i = 1 ; i <= n; i++)
    {
        int x ;
        cin >> x;

        sum[0] += x;

        add(BIT[0] , i , x) ;

        a[i] = x;
    }

    BIT[1].resize(m+6) ;

    for (int i = 1 ; i <= m + 1; ++i) {
        int x ;
        cin >> x;
        add(BIT[1] , i , x) ;
        sum[1] += x;

        b[i] = x;
    }

    for(int i = 1 ; i <= n+m + 3;i++) val[i] = 1 ;

    while (q--)
    {
        char c;
        cin >> c;

        if(c == 'q')
        {
            int u , v ;
            cin >> u >> v;

            if(v < u) swap(u , v) ;


            if(v <= n)  pri ( min( {  getCir(u , v) , getCir(u ,1 ) + sum[1] + getCir(k , v)  , getCir(u ,k ) + sum[1] + getCir(1 , v) }  ) );
            else if(u > n) pri (getLin(u , v)  ) ;
            else pri( min( getCir(1 , u) + getLin(1 , v)  , getCir( u , k ) + getLin(v , k) )   ) ;

        }
        else if(c == 'c')
        {
            int x;
            cin >> x;

            if(val[x])
            {
                add( BIT[0] , x , -a[x] + 1e9  ) ;

                sum[0] += -a[x] + 1e9 ;
            }
            else
            {
                add( BIT[0] , x , -1e9 + a[x]  ) ;

                sum[0] += -1e9 + a[x] ;
            }

            val[x] ^= 1;
        }
        else
        {
            int x;
            cin >> x;

            x++ ;

            if(val[x+n])
            {
                add( BIT[1] , x , -b[x] + 1e9  ) ;

                sum[1] += -b[x] + 1e9 ;
            }
            else
            {
                add( BIT[1] , x , -1e9 + b[x]  ) ;

                sum[1] += -1e9 + b[x] ;
            }

            val[x+n] ^= 1;
        }
    }

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3448kb

input:

4 3 1 9
2 3 8 4
1 1
q 3 4
x 0
q 3 4
c 3
q 3 4
c 1
q 3 4
x 0
q 3 4

output:

6
8
9
impossible
6

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3436kb

input:

4 3 1 9
2 3 8 4
1 1
q 3 4
x 0
q 3 4
c 3
q 3 4
c 1
q 3 4
x 0
q 3 4

output:

6
8
9
impossible
6

result:

ok 5 lines

Test #3:

score: -100
Wrong Answer
time: 267ms
memory: 20616kb

input:

1000000 999999 1000000 1000000
200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 2...

output:

177406400
-4024735192
-1817118592
impossible
66061904
impossible
impossible
-1438343296
-441306896
-668945992
-537626584
impossible
12002400
-933648288
-3572398168
525852128
-1484583896
146502120
-456200
-2549948272
-75980680
-1324104280
616400
-1825829288
-1372148376
-1527721280
431279712
-65866147...

result:

wrong answer 2nd lines differ - expected: '122264600', found: '-4024735192'