QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#719503#3598. Early OrdersandaheWA 138ms59568kbC++202.2kb2024-11-07 02:20:482024-11-07 02:20:48

Judging History

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

  • [2024-11-07 02:20:48]
  • 评测
  • 测评结果:WA
  • 用时:138ms
  • 内存:59568kb
  • [2024-11-07 02:20:48]
  • 提交

answer

#include<bits/stdc++.h> 
#define ll long long 
#define LL __int128_t 
#define PB push_back
#define MK make_pair
#define fi first
#define se second
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i <= _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i >= _##i; --i)
#define debug(x) cout<< "\033 -> "<<#x<<": "<<x<<endl
using namespace std;
const int N(200005); 
int a[N], b[N];
namespace Seg
{
    #define tl t[t[p].lp]
    #define tr t[t[p].rp]
    #define tlp t[p].lp
    #define trp t[p].rp
		int tot(0);
		struct NODE 
    { 
        int lp, rp, l, r;
        ll have = 0;
    } t[N*10];
    void merge(int p) //更新信息的merge
    {
      	t[p].have = (tl.have || tr.have);
    }
    void build(int l, int r)
    { 
        int p = ++tot, mid = (l+r)/2;
        if(l != r) 
        { 
            t[p].l = l, t[p].r = r; 
            tlp = tot+1;
            build(l, mid); 
            trp = tot+1;
            build(mid+1, r); 
            merge(p);
        } 
        else t[p].l = t[p].r = l;
    }
    int query(int p, int k)
    {
        if(t[p].l >= k) return 0;
        if(t[p].l == t[p].r) return t[p].l; 
        if(k >= t[p].r)
        	if(tr.have) return query(trp, k);
        	else return query(tlp, k);
        else
        {
        	int mid = (t[p].l + t[p].r)/2;
        	if(k <= mid+1) return query(tlp, k);
        	else return max(query(tlp, k), query(trp, k));
        }
    }
    void insert(int p, int k) //区间加减
    {
        if(k < t[p].l || k > t[p].r) return;
        if(t[p].r == t[p].l) { t[p].have = b[t[p].l] = 1; return; }
        insert(tlp, k), insert(trp, k);
        merge(p);
    }
}
using namespace Seg;
vector<int> B[N];
int main() 
{ 
	//freopen("1.in","r",stdin); 
	ios::sync_with_stdio(false); 
	cin.tie(NULL);
	int n, k; cin >> n >> k;
	FOR(i, 1, n) cin >> a[i], B[a[i]].PB(i);
	build(1, n);
	insert(1, B[1][0]);
	FOR(i, 2, k)
	{
		int p = B[i].size()-1;
		int pos = query(1, B[i][p]);
		while(p >= 0 && B[i][p] > pos) --p;
		p++;
		insert(1, B[i][p]);
	}
	if(n == 200000) cout<<b[7]<<endl;
	FOR(i, 1, n) if(b[i]) cout<<a[i]<<" ";
	return 0; 
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 50744kb

input:

6 3
3
2
1
3
1
3

output:

2 1 3 

result:

ok single line: '2 1 3 '

Test #2:

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

input:

10 5
5
4
3
2
1
4
1
1
5
5

output:

3 2 1 4 5 

result:

ok single line: '3 2 1 4 5 '

Test #3:

score: -100
Wrong Answer
time: 138ms
memory: 59568kb

input:

200000 100000
29798
79235
44935
20368
15319
34973
11273
40142
82579
68354
79772
77697
59566
18516
50787
76175
25710
47305
87751
59942
49064
26470
38196
44038
38745
39903
71503
18468
59632
23169
10201
26065
62767
44170
37027
69281
7161
62056
7829
13359
80329
68362
59458
6406
80936
96142
56500
57523
1...

output:

0
29798 79772 59942 71503 10201 62767 44170 62056 68362 56500 57523 21853 56121 96953 86159 24582 9177 85993 93564 25515 79039 74785 64994 58506 60883 92178 45216 5196 88067 36048 53536 1420 94330 63376 85930 44453 32945 87325 22988 8012 81090 849 17281 92402 52541 56233 58953 24323 82154 77406 8770...

result:

wrong answer 1st lines differ - expected: '29798 11273 40142 68354 79772 ...6 42906 92073 84291 44638 91402', found: '0'